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

DOI10.1016/J.JPDC.2006.08.011zbMATH Open1109.68131OpenAlexW2120459220MaRDI QIDQ868040FDOQ868040

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

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

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)

Cited In (8)

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

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)