An optimal parallel solution for the path cover problem on P₄-sparse graphs

DOI10.1016/J.JPDC.2006.08.011MaRDI QIDQ868040zbMATH OpenOpenAlexFDO

Authors Katerina Asdre, Stavros D. Nikolopoulos, Charis Papadopoulos

Publication date 19 February 2007

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2006.08.011

zbMATH Keywords

modular decompositionparallel algorithmspath covercographs\(P_{4}\)-sparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• A time-optimal solution for the path cover problem on cographs.
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• A fast parallel algorithm to recognize P4-sparse graphs
• An optimal path cover algorithm for cographs

Cited in

(8)

• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• A time-optimal solution for the path cover problem on cographs.
• Algorithms for solving problems on graphs of bounded pathwidth
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• A \(5k\)-vertex kernel for 3-path vertex cover
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

This page was built for publication: An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs

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