On CLIQUE Problem for Sparse Graphs of Large Dimension

DOI10.1007/978-3-319-13671-4_9MaRDI QIDQ3463541zbMATH OpenOpenAlexFDO

Authors Valentina Vladimirovna Bykova, Roman Illarionov

Publication date 19 January 2016

Published in Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13671-4_9

zbMATH Keywords

treewidthgraph algorithmssparse graphspreprocessingFPT-algorithmsatom graphbiphasic algorithmsdecomposition graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Recommendations

• scientific article; zbMATH DE number 1424314
• Enumerating maximal cliques in large sparse graphs
• Fast algorithms for the maximum clique problem on massive sparse graphs
• A new exact maximum clique algorithm for large and massive sparse graphs
• A linear time algorithm for maximal clique enumeration in large sparse graphs
• Fast maximal cliques enumeration in sparse graphs
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• Large cliques in sparse random intersection graphs
• On the approximability of clique and related maximization problems
• Clique cover on sparse networks

Cites work

• scientific article; zbMATH DE number 4039250 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithm 457: finding all cliques of an undirected graph
• Algorithms for maximum independent sets
• Decomposition by clique separators
• Mining market data: a network approach
• Optimal decomposition by clique separators

Cited in

(2)

• Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs

This page was built for publication: On CLIQUE Problem for Sparse Graphs of Large Dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3463541)