Dominating set is fixed parameter tractable in claw-free graphs

DOI10.1016/j.tcs.2011.09.010zbMath1228.68030arXiv1011.6239OpenAlexW2005475011MaRDI QIDQ650938

Marek Cygan, Marcin Pilipczuk, Geevarghese Philip, Jakub Onufry Wojtaszczyk, Michał Pilipczuk

Publication date: 7 December 2011

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

Full work available at URL: https://arxiv.org/abs/1011.6239

zbMATH Keywords

fixed parameter tractabilitycliquedominating setclaw-free graphsconnected dominating set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Shortest color-spanning intervals ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Perfect domination and small cycles ⋮ Unnamed Item ⋮ Parameterized domination in circle graphs ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Domination When the Stars Are Out ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Revising Johnson's table for the 21st century ⋮ Twin-width and polynomial kernels ⋮ Modifying a graph using vertex elimination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Claw-free graphs. VI: Colouring
• Dominating set is fixed parameter tractable in claw-free graphs
• Claw-free graphs. III: Circular interval graphs
• Claw-free graphs. IV: Decomposition theorem
• Claw-free graphs. V. Global structure
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Claw-free graphs---a survey
• Graph minors. XVI: Excluding a non-planar graph
• Claw-free graphs. I: Orientable prismatic graphs
• Claw-free graphs. II: Non-orientable prismatic graphs
• Parametrized complexity theory.
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Domination Problems in Nowhere-Dense Classes
• Domination When the Stars Are Out
• Deciding first-order properties of locally tree-decomposable structures
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Testing first-order properties for subclasses of sparse graphs
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations

This page was built for publication: Dominating set is fixed parameter tractable in claw-free graphs