New Polynomial Cases of the Weighted Efficient Domination Problem

DOI10.1007/978-3-642-40313-2_19zbMath1398.68218arXiv1304.6255OpenAlexW1796009870MaRDI QIDQ2849909

Ragnar Nevries, Martin Milanič, Andreas Brandstädt

Publication date: 20 September 2013

Published in: Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6255

zbMATH Keywords

polynomial-time algorithmrobust algorithmefficient domination\(P _{k }\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Efficient domination through eigenvalues ⋮ Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ A note on efficient domination in a superclass of \(P_5\)-free graphs ⋮ Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs

This page was built for publication: New Polynomial Cases of the Weighted Efficient Domination Problem