Domination problems with no conflicts

DOI10.1016/J.DAM.2018.03.018MaRDI QIDQ1752590zbMATH OpenOpenAlexWikidataFDO

Authors 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

conflictsdominating setforbidden pairsindependent dominating setNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• Total domination, connected vertex cover and Steiner tree with conflicts
• A decidability result for the dominating set problem
• Independent domination in finitely defined classes of graphs
• scientific article; zbMATH DE number 91051
• An induced subgraph characterization of domination perfect graphs

Cites work

• A simplified NP-complete satisfiability problem
• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Complexity of the path avoiding forbidden pairs problem revisited
• Finding paths in grids with forbidden transitions
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Nash-Williams-type and Chvátal-type conditions in one-conflict graphs
• On paths avoding forbidden pairs of vertices in a graph
• On the complexity of paths avoiding forbidden pairs
• Some Hamiltonian properties of one-conflict graphs
• Total domination, connected vertex cover and Steiner tree with conflicts
• Trees in graphs with conflict edges or forbidden transitions

Cited in

(4)

• On the complexity of independent dominating set with obligations in graphs
• Total domination, connected vertex cover and Steiner tree with conflicts
• Introduction to routing problems with mandatory transitions
• Fixed set search matheuristic applied to the knapsack problem with forfeits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752590)