Domination When the Stars Are Out

2011/01/01 by Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen +1 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Complement (music) #Complexity and Algorithms in Graphs #Connected dominating set #Discrete mathematics #Dominating set #Graph #Graph theory and applications #Line graph #Mathematics #Maximal independent set #Pathwidth #Split graph #Time complexity

paper · doi:10.1007/978-3-642-22006-7_39

crossref issued 2011/01/01 · crossref published 2011/01/01 · crossref published-print 2011/01/01 · openalex publication_date 2011/01/01 · crossref created 2011/06/20 · crossref deposited 2024/04/07 · crossref indexed 2024/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• Subclasses of Normal Helly Circular-Arc Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Optimal antithickenings of claw-free trigraphs
• On maximal independent sets of vertices in claw-free graphs
• Finding a Minimum Circuit in a Graph
• On domination and independent domination numbers of a graph
• Which Problems Have Strongly Exponential Complexity?
• Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
• Dominating set is fixed parameter tractable in claw-free graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• A max m,n algorithm for determining the graph H from its line graph G
• The Rectilinear Steiner Tree Problem is NP-Complete
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Approximation algorithms for combinatorial problems
• Fourier meets möbius: fast subset convolution
• Claw-free graphs. III. Circular interval graphs
• Claw-free graphs — A survey
• A threshold of ln n for approximating set cover
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Reducibility among Combinatorial Problems
• Approximation Algorithms for Connected Dominating Sets
• Paths, Trees, and Flowers

Cited by

• Claw-free graph [wikipedia]