Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Sciences
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
Computer Science Faculty Publications
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum path cover for a cograph G. In case G has a Hamiltonian path (cycle) our algorithm exhibits the path (cycle) as well.