Independence and efficient domination on P₆-free graphs
DOI10.1137/1.9781611974331.CH124zbMATH Open1409.68145OpenAlexW2949732571MaRDI QIDQ4575708FDOQ4575708
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
Recommendations
- Independence and Efficient Domination on P 6 -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
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)
Cited In (22)
- 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 6 -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 efficient domination for \(P_6\)-free and for \(P_5\)-free graphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time
- Boundary classes for graph problems involving non-local properties
- On efficient domination for some classes of \(H\)-free chordal graphs
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- New Polynomial Case for Efficient Domination in P 6-free Graphs
- Structure of squares and efficient domination in graph classes
- On efficient domination for some classes of \(H\)-free chordal graphs
- Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
- Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs
- Weighted efficient domination in two subclasses of \(P_6\)-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
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-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)
