Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive Graphs

Ronald D. Hagan; Charles A. Philips; Kai Wang; Gary L. Rogers; Michael A. Langston

doi:10.1109/BigData.2014.7004370

Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive Graphs

Ronald D. Hagan, Charles A. Philips, Kai Wang, Gary L. Rogers, Michael A. Langston

Computer Science

University of Tennessee, Knoxville

Research output: Contribution to book or proceeding › Chapter

2 Scopus citations

Abstract

As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial problems on graphs that may be too large to fit entirely in memory. In previous work, we have provided a set of out-of-core algorithms to solve one of the central examples of such a problem, maximum clique. In this paper, we review the algorithms and report on our ongoing work to use them as a starting point for an optimized, highly scalable implementation of a maximum clique solver.

Original language	American English
Title of host publication	Proceedings of the IEEE International Conference on Big Data
DOIs	https://doi.org/10.1109/BigData.2014.7004370
State	Published - Oct 27 2014

Keywords

Algorithm design and analysis
Big data
Conferences
Memory management
Optimization
Parallel algorithms
Roads
big data
maximum clique
out-of-core
parallel graph algorithms

DC Disciplines

Engineering
Computer Sciences

Access to Document

10.1109/BigData.2014.7004370License: Unspecified

Cite this

@inbook{5d675a0b58cb4e9e87ea24d810faa52a,

title = "Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive Graphs",

abstract = " As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial problems on graphs that may be too large to fit entirely in memory. In previous work, we have provided a set of out-of-core algorithms to solve one of the central examples of such a problem, maximum clique. In this paper, we review the algorithms and report on our ongoing work to use them as a starting point for an optimized, highly scalable implementation of a maximum clique solver.",

keywords = "Algorithm design and analysis, Big data, Conferences, Memory management, Optimization, Parallel algorithms, Roads, big data, maximum clique, out-of-core, parallel graph algorithms",

author = "Hagan, {Ronald D.} and Philips, {Charles A.} and Kai Wang and Rogers, {Gary L.} and Langston, {Michael A.}",

note = "As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial pr",

year = "2014",

month = oct,

day = "27",

doi = "10.1109/BigData.2014.7004370",

language = "American English",

booktitle = "Proceedings of the IEEE International Conference on Big Data",

}

TY - CHAP

T1 - Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive Graphs

AU - Hagan, Ronald D.

AU - Philips, Charles A.

AU - Wang, Kai

AU - Rogers, Gary L.

AU - Langston, Michael A.

N1 - As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial pr

PY - 2014/10/27

Y1 - 2014/10/27

N2 - As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial problems on graphs that may be too large to fit entirely in memory. In previous work, we have provided a set of out-of-core algorithms to solve one of the central examples of such a problem, maximum clique. In this paper, we review the algorithms and report on our ongoing work to use them as a starting point for an optimized, highly scalable implementation of a maximum clique solver.

AB - As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial problems on graphs that may be too large to fit entirely in memory. In previous work, we have provided a set of out-of-core algorithms to solve one of the central examples of such a problem, maximum clique. In this paper, we review the algorithms and report on our ongoing work to use them as a starting point for an optimized, highly scalable implementation of a maximum clique solver.

KW - Algorithm design and analysis

KW - Big data

KW - Conferences

KW - Memory management

KW - Optimization

KW - Parallel algorithms

KW - Roads

KW - big data

KW - maximum clique

KW - out-of-core

KW - parallel graph algorithms

UR - https://doi.org/10.1109/BigData.2014.7004370

U2 - 10.1109/BigData.2014.7004370

DO - 10.1109/BigData.2014.7004370

M3 - Chapter

BT - Proceedings of the IEEE International Conference on Big Data

ER -

Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive Graphs

Abstract

Keywords

DC Disciplines

Access to Document

Other files and links

Fingerprint

Cite this