On CLIQUE Problem for Sparse Graphs of Large Dimension

DOI10.1007/978-3-319-13671-4_9zbMATH Open1336.05077OpenAlexW43306143MaRDI QIDQ3463541FDOQ3463541

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

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

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)

Cites Work

• Algorithm 457: finding all cliques of an undirected graph
• Title not available (Why is that?)
• Mining market data: a network approach
• Decomposition by clique separators
• Optimal decomposition by clique separators
• Algorithms for maximum independent sets
• Title not available (Why is that?)

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)