A time-optimal solution for the path cover problem on cographs.

DOI10.1016/S0304-3975(02)00068-3MaRDI QIDQ1401176zbMATH OpenOpenAlexFDO

Authors Koji Nakano, Stephan Olariu, Albert Y. Zomaya

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00068-3

zbMATH Keywords

vertex cograph

Mathematics Subject Classification ID

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

Recommendations

• An optimal path cover algorithm for cographs
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
• Optimal covering of cacti by vertex-disjoint paths
• Partial and perfect path covers of cographs
• Efficient parallel recognition of cographs

Cites work

• A simple parallel tree contraction algorithm
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• An Efficient Parallel Biconnectivity Algorithm
• An optimal path cover algorithm for cographs
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Complement reducible graphs
• Deterministic parallel list ranking
• Efficient parallel algorithms for graph problems
• Graph theory
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• Parallel Algorithm for Cograph Recognition with Applications
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(21)

• Optimal covering of cacti by vertex-disjoint paths
• Optimal path cover problem on block graphs and bipartite permutation graphs
• An optimal path cover algorithm for cographs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Computing directed Steiner path covers
• Distance eigenvalues of a cograph and their multiplicities
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Cographs: eigenvalues and Dilworth number
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor
• The Hamiltonian problem on distance-hereditary graphs
• Efficient parallel recognition of cographs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Linear-time algorithm for the matched-domination problem in cographs
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• scientific article; zbMATH DE number 1151806 (Why is no real title available?)
• \(\mathcal Q\)-cospectrality and \(\mathcal L\)-energy in cographs
• Spectral properties of cographs and P₅-free graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• Seidel matrices, Dilworth number and an eigenvalue-free interval for cographs
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs

This page was built for publication: A time-optimal solution for the path cover problem on cographs.

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