On the complexity of fixed parameter clique and dominating set
From MaRDI portal
Publication:703534
DOI10.1016/j.tcs.2004.05.009zbMath1071.68030OpenAlexW1973113631WikidataQ56210401 ScholiaQ56210401MaRDI QIDQ703534
Fabrizio Grandoni, Friedrich Eisenbrand
Publication date: 11 January 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.05.009
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Counting Subgraphs in Degenerate Graphs, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Map graphs having witnesses of large girth, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Exact Weight Subgraphs and the k-Sum Conjecture, Induced subgraph isomorphism: are some patterns substantially easier than others?, A faster interior-point method for sum-of-squares optimization, Streaming deletion problems Parameterized by vertex cover, Arboricity, \(h\)-index, and dynamic algorithms, On linear algebraic algorithms for the subgraph matching problem and its variants, Unnamed Item, Finding small complete subgraphs efficiently, On Approximating the Number of $k$-Cliques in Sublinear Time, Are unique subgraphs not easier to find?, Hardness of RNA folding problem with four symbols, A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques, A fast deterministic detection of small pattern graphs in graphs without large cliques, Open problems around exact algorithms, Unnamed Item, Detecting and Counting Small Pattern Graphs, Algebraic methods in the congested clique, Efficient algorithms for clique problems, Intersection graphs of non-crossing paths, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, When can graph hyperbolicity be computed in linear time?, Counting Subgraphs in Relational Event Graphs, Beating treewidth for average-case subgraph isomorphism, Detecting and enumerating small induced subgraphs in \(c\)-closed graphs, Rare siblings speed-up deterministic detection and counting of small pattern graphs, Fine-Grained Reductions and Quantum Speedups for Dynamic Programming., A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction, Logical complexity of induced subgraph isomorphism for certain families of graphs, Unique subgraphs are not easier to find, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
Cites Work
- Finding and counting small induced subgraphs efficiently
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding and counting given length cycles
- Matrix multiplication via arithmetic progressions
- Fast rectangular matrix multiplication and applications
- Rectangular matrix multiplication revisited
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Finding a Minimum Circuit in a Graph
- On Syntactic versus Computational Views of Approximability
- Algorithms and Data Structures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
