Domination problems with no conflicts

DOI10.1016/j.dam.2018.03.018zbMath1387.05181OpenAlexW2795155838WikidataQ130052195 ScholiaQ130052195MaRDI QIDQ1752590

Alexis Cornet, Christian Laforest

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.03.018

zbMATH Keywords

NP-completenessdominating setindependent dominating setforbidden pairsconflicts

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Introduction to routing problems with mandatory transitions ⋮ On the complexity of independent dominating set with obligations in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On paths avoding forbidden pairs of vertices in a graph
• A simplified NP-complete satisfiability problem
• On the complexity of paths avoiding forbidden pairs
• Complexity of the path avoiding forbidden pairs problem revisited
• Finding Paths in Grids with Forbidden Transitions
• An Exact Algorithm to Check the Existence of (Elementary) Paths and a Generalisation of the Cut Problem in Graphs with Forbidden Transitions
• Some Hamiltonian Properties of One-Conflict Graphs
• Trees in Graphs with Conflict Edges or Forbidden Transitions
• Nash-Williams-type and Chvátal-type Conditions in One-Conflict Graphs

This page was built for publication: Domination problems with no conflicts