AN OPTIMAL PATH COVER ALGORITHM FOR COGRAPHS

Authors
LIN R OLARIU S PRUESSE G
Citation
R. Lin et al., AN OPTIMAL PATH COVER ALGORITHM FOR COGRAPHS, Computers & mathematics with applications, 30(8), 1995, pp. 75-83
Citations number
14
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
30
Issue
8
Year of publication
1995
Pages
75 - 83
Database
ISI
SICI code
0898-1221(1995)30:8<75:AOPCAF>2.0.ZU;2-9
Abstract
The class of cographs, or complement-reducible graphs, arises naturall y in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a mini mum path cover for a cograph G. In case G has a Hamiltonian path (cycl e) our algorithm exhibits the path (cycle) as well.