On the complexity of independent dominating set with obligations in graphs

DOI10.1016/j.tcs.2021.05.018OpenAlexW3089228560MaRDI QIDQ2072059

Timothée Martinod, Christian Laforest

Publication date: 1 February 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.018

zbMATH Keywords

domination\textit{NP}-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

In memory of Jérôme Monnot ⋮ Introduction to routing problems with mandatory transitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• On approximating the minimum independent dominating set
• Domination problems with no conflicts
• Graph problems with obligations
• 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
• Algorithms – ESA 2004

This page was built for publication: On the complexity of independent dominating set with obligations in graphs