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

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

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₆-free and for P₅-free graphs
• Weighted efficient domination for P₅-free and P₆-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(23)

• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-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₁, H₂)-free graphs
• Efficient domination for classes of \(P_6\)-free graphs
• 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
• Efficient domination for some subclasses of P₆-free graphs in polynomial time
• Weighted efficient domination for P₅-free and P₆-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs
• Weighted efficient domination for P₆-free and for P₅-free graphs
• The maximum weight stable set problem in (P₆, bull)-free graphs
• Structure of squares and efficient domination in graph classes
• Independence and Efficient Domination on P ₆ -free Graphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• Combining decomposition approaches for the maximum weight stable set problem
• A study on the weighted efficient domination problem for C₄-free bipartite graphs
• Weighted independent sets in a subclass of P₆-free graphs
• Weighted efficient domination in two subclasses of P₆-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)