An exact algorithm for the minimum dominating clique problem
From MaRDI portal
Publication:2456374
DOI10.1016/j.tcs.2007.06.014zbMath1125.68135OpenAlexW2151708662MaRDI QIDQ2456374
Mathieu Liedloff, Dieter Kratsch
Publication date: 18 October 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.06.014
Related Items
Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms] ⋮ Exact algorithms for dominating set ⋮ The complexity of connected dominating sets and total dominating sets with specified induced subgraphs ⋮ Algorithms for dominating clique problems ⋮ New results on connected dominating structures in graphs ⋮ Threshold dominating cliques in random graphs and interval routing ⋮ On connected dominating sets of restricted diameter
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generating all maximal independent sets
- A note on the complexity of the chromatic number problem
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A note on the complexity of minimum dominating set
- A Dynamic Programming Approach to Sequencing Problems
- A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Algorithms for maximum independent sets
- Finding a Maximum Independent Set
- Parameterized and Exact Computation
- Solving Connected Dominating Set Faster Than 2 n
- STACS 2005
- Graph-Theoretic Concepts in Computer Science
- Automata, Languages and Programming
- Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
- Exact Computation of Maximum Induced Forest
- On cliques in graphs
- Dominating cliques in graphs
