Using out-of-core techniques to produce exact solutions to the maximum clique problem on extremely large graphs

Author

Rogers, Gary L. ; Perkins, Andy D. ; Phillips, Charles A. ; Eblen, John D. ; Abu-Khzam, Faisal N. ; Langston, Michael A.

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., Univ. of Tennessee, Knoxville, TN

fYear

2009

fDate

10-13 May 2009

Firstpage

374

Lastpage

381

Abstract

Practical methods are presented for computing exact solutions to the maximum clique problem on graphs that are too large to fit within core memory. These methods use a combination of in-core and out-of-core techniques, recursively dissecting large graphs into manageable components. A global solution to the maximum clique problem is derived from local solutions generated for each of the individual components. Parallelizing the search within these components is instrumental in improving the running times of the algorithms.

Keywords

graph theory; parallel algorithms; search problems; storage management; core memory; extreme large graph; manageable component; maximum clique problem; out-of-core technique; parallel algorithm; search problem; Biology computing; Broadcasting; Computational biology; Computer science; Computer vision; Concurrent computing; Distributed computing; Instruments; Mathematics; Memory management;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Systems and Applications, 2009. AICCSA 2009. IEEE/ACS International Conference on

Conference_Location

Rabat

Print_ISBN

978-1-4244-3807-5

Electronic_ISBN

978-1-4244-3806-8

Type

conf

DOI

10.1109/AICCSA.2009.5069351

Filename

5069351