Improved algorithms for k-domination and total k-domination in proper interval graphs

DOI10.1007/978-3-319-96151-4_25MaRDI QIDQ1661898zbMATH OpenOpenAlexFDO

Authors Nina Chiarelli, Tatiana Romina Hartinger, V. Leoni, Maria Inés Lopez Pujato, Martin Milanič

Publication date 17 August 2018

Full work available at URL https://doi.org/10.1007/978-3-319-96151-4_25

zbMATH Keywords

polynomial-time algorithmproper interval graph\(k\)-dominationtotal \(k\)-domination

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• Total 2-domination of proper interval graphs
• On the algorithmic complexity of \(k\)-tuple total domination
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs

Cited in

(7)

• Mim-width. III. Graph powers and generalized distance domination problems
• A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
• Total 2-domination of proper interval graphs
• The k-neighbor, r-domination problems on interval graphs
• Defensive domination in proper interval graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• Multiple domination

This page was built for publication: Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs

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