Efficient algorithms for clique problems
From MaRDI portal
Publication:976087
DOI10.1016/J.IPL.2008.10.014zbMATH Open1191.68455OpenAlexW2155978818MaRDI QIDQ976087FDOQ976087
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
Recommendations
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Parameterized clique on inhomogeneous random graphs
- Finding hidden cliques in linear time with high probability
- ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)
Cites Work
- Gaussian elimination is not optimal
- Title not available (Why is that?)
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Title not available (Why is that?)
- Color-coding
- Finding and counting given length cycles
- Matrix multiplication via arithmetic progressions
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Finding and counting small induced subgraphs efficiently
- Title not available (Why is that?)
- Fast recognition of pushdown automaton and context-free languages
- Finding a Minimum Circuit in a Graph
- Title not available (Why is that?)
- Algorithms for maximum independent sets
- Linear FPT reductions and computational lower bounds
- Divide-and-Color
- Measure and conquer
- Parameterized and Exact Computation
- On the complexity of fixed parameter clique and dominating set
Cited In (17)
- A linear time algorithm for maximal clique enumeration in large sparse graphs
- A post-quantum associative memory
- Large clique is hard on average for resolution
- An Efficient Algorithm for Enumerating Pseudo Cliques
- Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
- Counting Homomorphic Cycles in Degenerate Graphs
- On Approximating the Number of $k$-Cliques in Sublinear Time
- Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
- Computing the depth distribution of a set of boxes
- Pushdown reachability with constant treewidth
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Title not available (Why is that?)
- Tight conditional lower bounds for vertex connectivity problems
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Counting Subgraphs in Degenerate Graphs
- Hardness of RNA folding problem with four symbols
- Faster combinatorial \(k\)-clique algorithms
This page was built for publication: Efficient algorithms for clique problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976087)
