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

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Rogers, G.L., Perkins, A.D., Phillips, C.A., Eblen, J.D., Abu-Khzam, F.N., Langston, M.A.
Format: Conference Proceeding
Language:English
Subjects:
Biology computing
Broadcasting
Computational biology
Computer science
Computer vision
Concurrent computing
Distributed computing
Instruments
Mathematics
Memory management
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2161-5322
2161-5330
DOI:10.1109/AICCSA.2009.5069351