On the computational complexity of path cover problems

DOI10.1016/0022-0000(84)90032-1MaRDI QIDQ799105zbMATH OpenOpenAlexFDO

Authors 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 digraphsacyclic structured digraphspath cover problemsreachability relationrooted trees

Mathematics Subject Classification ID

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

Recommendations

• Covering pairs in directed acyclic graphs
• Complexité de problèmes liés aux graphes sans circuit
• scientific article; zbMATH DE number 3876620
• On legal path problems in digraphs
• Cardinality constrained path covering problems in grid graphs

Cites work

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

Cited in

(16)

• Complexity of path discovery game problems
• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Path covering problems and testing of printed circuits
• On the \(k\)-path cover problem for cacti
• Complexity of the path avoiding forbidden pairs problem revisited
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• The Complexity of Restricted Variants of the Stable Paths Problem
• Cardinality constrained path covering problems in grid graphs
• Path Problems in Structured Graphs
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• The computational complexity of optimal blocking of vertices in the digraph
• Covering pairs in directed acyclic graphs
• On legal path problems in digraphs
• On the complexity of recognizing directed path families
• On the complexity of paths avoiding forbidden pairs

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

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