A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

DOI10.1002/net.20200zbMath1135.68502OpenAlexW4242310348MaRDI QIDQ5434590

Stavros D. Nikolopoulos, Katerina Asdre

Publication date: 7 January 2008

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20200

zbMATH Keywords

perfect graphscographslinear-time algorithmspath covercotreecomplement reducible graphsfixed-endpoint path cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs

Cites Work

• Graph Classes: A Survey
• Unnamed Item

This page was built for publication: A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs