Algorithms for dominating clique problems

DOI10.1016/J.TCS.2012.07.016MaRDI QIDQ1758169zbMATH OpenOpenAlexFDO

Authors Bruno Escoffier, Vangelis Th. Paschos, Nicolas Bourgeois, F. Della Croce

Publication date 8 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.07.016

zbMATH Keywords

exponential time algorithmsdominating cliqueexact and approximation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Exact algorithms for dominating clique problems (extended abstract)
• An exact algorithm for the minimum dominating clique problem
• An Exact Algorithm for the Minimum Dominating Clique Problem
• On the complexity of fixed parameter clique and dominating set
• Graph-Theoretic Concepts in Computer Science

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1124601 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• Algorithms for maximum independent sets
• An exact algorithm for the minimum dominating clique problem
• An exponential time 2-approximation algorithm for bandwidth
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of min coloring by moderately exponential algorithms
• Clustering and domination in perfect graphs
• Dominating cliques in graphs
• Dominating sets in social network graphs
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Enumerating maximal independent sets with applications to graph colouring.
• Exact and approximate bandwidth
• Exponential-time approximation of weighted set cover
• Fast algorithms for max independent set
• On cliques in graphs
• On generating all maximal independent sets
• Set partitioning via inclusion-exclusion
• Which problems have strongly exponential complexity?

Cited in

(6)

• On identifying dominant cliques.
• Dominating cliques in graphs
• Exact algorithms for dominating clique problems (extended abstract)
• An exact algorithm for the minimum dominating clique problem
• An Exact Algorithm for the Minimum Dominating Clique Problem
• Inclusion/exclusion meets measure and conquer

This page was built for publication: Algorithms for dominating clique problems

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