Independence and Efficient Domination on P6-free Graphs

DOI10.1137/1.9781611974331.ch124zbMath1409.68145OpenAlexW2949732571MaRDI QIDQ4575708

Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch124

Mathematics Subject Classification ID

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

Related Items (19)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Boundary classes for graph problems involving non-local properties ⋮ A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Efficient domination for classes of \(P_6\)-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

This page was built for publication: Independence and Efficient Domination on P₆-free Graphs