Algorithms for dominating clique problems

DOI10.1016/j.tcs.2012.07.016zbMath1252.05160OpenAlexW2048060811MaRDI QIDQ1758169

Vangelis Th. Paschos, Bruno Escoffier, Nicolas Bourgeois, Frederico 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

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

Related Items (1)

Inclusion/exclusion meets measure and conquer

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Enumerating maximal independent sets with applications to graph colouring.
• Exact and approximate bandwidth
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Clustering and domination in perfect graphs
• Dominating sets in social network graphs
• On generating all maximal independent sets
• Which problems have strongly exponential complexity?
• Fast algorithms for max independent set
• An exact algorithm for the minimum dominating clique problem
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• A measure & conquer approach for the analysis of exact algorithms
• Set Partitioning via Inclusion-Exclusion
• An Exponential Time 2-Approximation Algorithm for Bandwidth
• Algorithms for maximum independent sets
• On cliques in graphs
• Dominating cliques in graphs

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