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

rooted treesacyclic digraphsacyclic structured digraphspath cover problemsreachability relation

Mathematics Subject Classification ID

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

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

• 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
• `` Strong NP-Completeness Results

Cited in

(16)

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

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)