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

DOI10.1016/S0304-3975(02)00068-3zbMath1038.68087OpenAlexW2028704451MaRDI QIDQ1401176

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)

Related Items (11)

The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Distance eigenvalues of a cograph and their multiplicities ⋮ -cospectrality and -energy in cographs ⋮ The Hamiltonian problem on distance-hereditary graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Spectral properties of cographs andP₅-free graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Cographs: eigenvalues and Dilworth number ⋮ Efficient parallel recognition of cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic parallel list ranking
• Complement reducible graphs
• Efficient parallel algorithms for graph problems
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• An optimal path cover algorithm for cographs
• Parallel Algorithm for Cograph Recognition with Applications
• An Efficient Parallel Biconnectivity Algorithm
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• A simple parallel tree contraction algorithm
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS

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