An exact algorithm for the minimum dominating clique problem

DOI10.1016/J.TCS.2007.06.014MaRDI QIDQ2456374zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Mathieu Liedloff

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

zbMATH Keywords

dominating setgraph algorithmsexponential time algorithmsdominating clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• An Exact Algorithm for the Minimum Dominating Clique Problem
• Exact algorithms for dominating clique problems (extended abstract)
• Algorithms for dominating clique problems
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 4045183

Cites work

• scientific article; zbMATH DE number 5604103 (Why is no real title available?)
• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1124601 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• A Dynamic Programming Approach to Sequencing Problems
• A note on the complexity of minimum dominating set
• A note on the complexity of the chromatic number problem
• Algorithms for maximum independent sets
• Automata, Languages and Programming
• Dominating cliques in graphs
• Exact Computation of Maximum Induced Forest
• Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
• Finding a Maximum Independent Set
• Graph-Theoretic Concepts in Computer Science
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• On cliques in graphs
• On generating all maximal independent sets
• Parameterized and Exact Computation
• STACS 2005
• Solving Connected Dominating Set Faster Than 2 n

Cited in

(15)

• Analysis and computation of the outcomes of pure Nash equilibria in two-player extensive-form games
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Exact algorithms for dominating set
• New results on connected dominating structures in graphs
• Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms
• Exact algorithms for the minimum cost vertex blocker clique problem
• Algorithms for dominating clique problems
• scientific article; zbMATH DE number 2222002 (Why is no real title available?)
• On connected dominating sets of restricted diameter
• Exact algorithms for dominating clique problems (extended abstract)
• Finding minimum clique capacity
• Threshold dominating cliques in random graphs and interval routing
• An Exact Algorithm for the Minimum Dominating Clique Problem
• scientific article; zbMATH DE number 4045183 (Why is no real title available?)
• Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes

This page was built for publication: An exact algorithm for the minimum dominating clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2456374)