Dominating set is fixed parameter tractable in claw-free graphs

2011/09/16 by Marek Cygan, Geevarghese Philip, Marcin Pilipczuk +2 · 20 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Chordal graph #Cograph #Combinatorics #Discrete mathematics #Dominating set #Graph #Independent set #Induced subgraph #Induced subgraph isomorphism problem #Line graph #Mathematics #Maximal independent set #Parameterized complexity #Pathwidth #Split graph #Vertex (graph theory) #Voltage graph

paper · pdf · doi:10.1016/j.tcs.2011.09.010

published in Theoretical Computer Science 412(50), 6982-7000 (Elsevier BV)

openalex publication_date 2011/09/16 · crossref created 2011/09/16 · crossref issued 2011/11/01 · crossref published 2011/11/01 · crossref published-print 2011/11/01 · crossref deposited 2021/12/05 · crossref indexed 2025/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Citations

• Invitation to Fixed-Parameter Algorithms
• Extremal Combinatorics
• Parameterized Complexity Theory
• Efficient Approximation for Triangulation of Minimum Treewidth
• On maximal independent sets of vertices in claw-free graphs
• Deciding first-order properties of locally tree-decomposable structures
• Claw-free graphs VI. Colouring
• Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
• Graph Minors. XVI. Excluding a non-planar graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Claw-free graphs. III. Circular interval graphs
• Deciding First-Order Properties for Sparse Graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Claw-free graphs — A survey
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Reducibility among Combinatorial Problems

Cited by

• Domination When the Stars Are Out
• Claw-free graph [wikipedia]