On the complexity of fixed parameter clique and dominating set
From MaRDI portal
Recommendations
- On the parameterized complexity of approximating dominating set
- On the Parameterized Complexity of Approximating Dominating Set
- On hardness of approximating the parameterized clique problem
- Parameterized approximation of dominating set problems
- Exact algorithms for dominating clique problems (extended abstract)
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- scientific article; zbMATH DE number 1617251
- The parameterized complexity of dominating set and friends revisited for structured graphs
- Parameterized complexity of minimum membership dominating set
- Parameterized complexity of minimum membership dominating set
Cites work
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 3188526 (Why is no real title available?)
- Algorithms and Data Structures
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Fast rectangular matrix multiplication and applications
- Finding a Minimum Circuit in a Graph
- Finding and counting given length cycles
- Finding and counting small induced subgraphs efficiently
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Matrix multiplication via arithmetic progressions
- On Syntactic versus Computational Views of Approximability
- Rectangular matrix multiplication revisited
Cited in
(56)- Listing 4-cycles
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- scientific article; zbMATH DE number 7561323 (Why is no real title available?)
- On the Parameterized Complexity of Approximating Dominating Set
- Faster algorithms for all-pairs bounded min-cuts
- scientific article; zbMATH DE number 1617251 (Why is no real title available?)
- Open problems around exact algorithms
- When can graph hyperbolicity be computed in linear time?
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Efficient algorithms for clique problems
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Detecting and counting small pattern graphs
- On the fine-grained complexity of approximating max k-coverage
- Unique subgraphs are not easier to find
- An enumerative perspective on connectivity
- Approximately counting independent sets of a given size in bounded-degree graphs
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- If the current clique algorithms are optimal, so is Valiant's parser
- Algorithms for dominating clique problems
- Map graphs having witnesses of large girth
- Logical complexity of induced subgraph isomorphism for certain families of graphs
- A faster interior-point method for sum-of-squares optimization
- Tensor network complexity of multilinear maps
- Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
- Arboricity, \(h\)-index, and dynamic algorithms
- Finding and counting patterns in sparse graphs
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Counting connected subgraphs with maximum-degree-aware sieving
- Rare siblings speed-up deterministic detection and counting of small pattern graphs
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- Finding small complete subgraphs efficiently
- Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
- Intersection graphs of non-crossing paths
- Beating treewidth for average-case subgraph isomorphism
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- Faster combinatorial k-clique algorithms
- Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
- Detecting disjoint shortest paths in linear time and more
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Finding and counting small tournaments in large tournaments
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Exact weight subgraphs and the k-sum conjecture
- The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
- On the query complexity of clique size and maximum satisfiability
- On approximating the number of k-cliques in sublinear time
- Counting subgraphs in relational event graphs
- Counting Subgraphs in Degenerate Graphs
- Sidestepping barriers for dominating set in parameterized complexity
- Are unique subgraphs not easier to find?
- Hardness of RNA folding problem with four symbols
- On the first-order complexity of induced subgraph isomorphism
- Faster combinatorial \(k\)-clique algorithms
- Streaming deletion problems Parameterized by vertex cover
This page was built for publication: On the complexity of fixed parameter clique and dominating set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703534)
