Domination When the Stars Are Out

DOI10.1007/978-3-642-22006-7_39zbMath1334.68160arXiv1012.0012OpenAlexW3147303226WikidataQ128003225 ScholiaQ128003225MaRDI QIDQ3012826

Matthias Mnich, Gerhard J. Woeginger, Danny Hermelin, Erik Jan van Leeuwen

Publication date: 6 July 2011

Published in: ACM Transactions on Algorithms, Automata, Languages and Programming (Search for Journal in Brave)

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

zbMATH Keywords

dominating setclaw-free graphsconnected dominating setpolynomial kernelfixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (20)

Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Equimatchable claw-free graphs ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Disconnected cuts in claw-free graphs ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Unnamed Item ⋮ Parameterized domination in circle graphs ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Contracting to a longest path in H-free graphs ⋮ Intersection graphs of non-crossing paths ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ Revising Johnson's table for the 21st century ⋮ Twin-width and polynomial kernels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating set is fixed parameter tractable in claw-free graphs
• On domination and independent domination numbers of a graph
• The stable set polytope of quasi-line graphs
• Claw-free graphs. V. Global structure
• On problems without polynomial kernels
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Linear time algorithms on circular-arc graphs
• Constrained weighted matchings and edge coverings in graphs
• Claw-free graphs---a survey
• A threshold of ln n for approximating set cover
• Coloring quasi-line graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Edge Dominating Sets in Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Parameterized and Exact Computation
• Paths, Trees, and Flowers

This page was built for publication: Domination When the Stars Are Out