Efficient algorithms for clique problems

DOI10.1016/j.ipl.2008.10.014zbMath1191.68455OpenAlexW2155978818MaRDI QIDQ976087

Virginia Vassilevska Williams

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.014

zbMATH Keywords

algorithmscombinatorial problemsgraph algorithmsclique

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Counting Subgraphs in Degenerate Graphs ⋮ A linear time algorithm for maximal clique enumeration in large sparse graphs ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Pushdown reachability with constant treewidth ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ A post-quantum associative memory ⋮ On linear algebraic algorithms for the subgraph matching problem and its variants ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Hardness of RNA folding problem with four symbols ⋮ Unnamed Item ⋮ Computing the depth distribution of a set of boxes ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Large clique is hard on average for resolution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• Finding and counting given length cycles
• On the complexity of fixed parameter clique and dominating set
• Matrix multiplication via arithmetic progressions
• Gaussian elimination is not optimal
• Divide-and-Color
• Linear FPT reductions and computational lower bounds
• Measure and conquer
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Fast recognition of pushdown automaton and context-free languages
• Algorithms for maximum independent sets
• Finding a Minimum Circuit in a Graph
• Color-coding
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Parameterized and Exact Computation