On the computational complexity of path cover problems

DOI10.1016/0022-0000(84)90032-1zbMath0547.68044OpenAlexW1988301526MaRDI QIDQ799105

Simeon C. Ntafos, Teofilo F. Gonzalez

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90032-1

zbMATH Keywords

acyclic digraphsrooted treesacyclic structured digraphspath cover problemsreachability relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Path covering problems and testing of printed circuits ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths

Cites Work

• A method and two algorithms on the theory of partitions
• A decomposition theorem for partially ordered sets
• On structured digraphs and program testing
• `` Strong NP-Completeness Results
• On Path Cover Problems in Digraphs and Applications to Program Testing

This page was built for publication: On the computational complexity of path cover problems