A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

DOI10.1007/S00607-008-0005-8zbMath1161.05336OpenAlexW1993725177MaRDI QIDQ938338

Elisabeth Gassner, Johannes Hatzl

Publication date: 19 August 2008

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-008-0005-8

zbMATH Keywords

distance-hereditary graphsbounded treewidthneighbourhood dominationparity constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Generalized threshold processes on graphs ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Combinatorial properties of a general domination problem with parity constraints ⋮ A Survey of the Game “Lights Out!”

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Combinatorial properties of a general domination problem with parity constraints
• Distance-hereditary graphs
• Dominating sets in social network graphs
• Linear cellular automata and the garden-of-eden
• Centers and medians of distance-hereditary graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• The Hamiltonian problem on distance-hereditary graphs
• Computing maximum stable sets for distance-hereditary graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• On non-z(mod k) dominating sets
• Capacitated Domination Problem
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Domination in distance-hereditary graphs

This page was built for publication: A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs