A simple optimal algorithm for k-tuple dominating problem in interval graphs

DOI10.1007/S10878-022-00932-4MaRDI QIDQ2102897zbMATH OpenOpenAlexFDO

Authors Peng Li, Aifa Wang, Jianhui Shang

Publication date 12 December 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-022-00932-4

zbMATH Keywords

dominationinterval graphlinear time algorithm\(k\)-tuple domination\(k\)-dominationtotal \(k\)-domination

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Minimum 2-tuple dominating set of an interval graph
• \(k\)-tuple domination in graphs
• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
• On the algorithmic complexity of \(k\)-tuple total domination
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs

Cites work

• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 19197 (Why is no real title available?)
• scientific article; zbMATH DE number 1057882 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• scientific article; zbMATH DE number 4121429 (Why is no real title available?)
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A unified approach to domination problems on interval graphs
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Algorithmic graph theory and perfect graphs
• Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Graph classes with structured neighborhoods and algorithmic applications
• Minimum 2-tuple dominating set of an interval graph
• Minimum 2-tuple dominating set of permutation graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• On \(k\)-domination and \(j\)-independence in graphs
• On the algorithmic complexity of \(k\)-tuple total domination
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the total \(k\)-domination number of graphs
• Onk-domination and minimum degree in graphs
• Optimal greedy algorithms for indifference graphs
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• The longest cycle problem is polynomial on interval graphs
• Trees with equal 2-domination and 2-independence numbers
• \(k\)-domination and \(k\)-independence in graphs: A survey
• \(k\)-tuple total domination in graphs

Cited in

(5)

• More on the complexity of defensive domination in graphs
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• Minimum 2-tuple dominating set of an interval graph
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs

This page was built for publication: A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs

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