Independence and efficient domination on P₆-free graphs

DOI10.1137/1.9781611974331.CH124MaRDI QIDQ4575708zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Independence and Efficient Domination on P ₆ -free Graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Weighted efficient domination for \(P_6\)-free and for \(P_5\)-free graphs
• Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(22)

• 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
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
• Independence and Efficient Domination on P ₆ -free Graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Combining decomposition approaches for the maximum weight stable set problem
• Weighted independent sets in classes of \(P_6\)-free graphs
• Weighted efficient domination for \(P_6\)-free and for \(P_5\)-free graphs
• Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time
• Boundary classes for graph problems involving non-local properties
• Weighted independent sets in a subclass of P₆-free graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Structure of squares and efficient domination in graph classes
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs
• Weighted efficient domination in two subclasses of P₆-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Efficient domination for classes of \(P_6\)-free graphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

This page was built for publication: Independence and efficient domination on \(P_6\)-free graphs

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