On Path Cover Problems in Digraphs and Applications to Program Testing

DOI10.1109/TSE.1979.234213MaRDI QIDQ4199539zbMATH OpenOpenAlexFDO

Authors S. Louis Hakimi, Simeon C. Ntafos

Publication date 1979

Published in IEEE Transactions on Software Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tse.1979.234213

zbMATH Keywords

algorithmic complexityDilworth numberprogram testingacyclic digraphspath cover problems in digraphs

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) Specification and verification (program logics, model checking, etc.) (68Q60)

Cited in

(38)

• How to guard a graph?
• Algorithms for finding disjoint path covers in unit interval graphs
• Path covering number and \(L(2,1)\)-labeling number of graphs
• Vertex covering by paths on trees with its applications in machine translation
• Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
• One-to-one disjoint path covers on k-ary n-cubes
• The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks
• Paired many-to-many disjoint path covers in restricted hypercube-like graphs
• One-to-one disjoint path covers on alternating group graphs
• Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs
• On the computational complexity of path cover problems
• Disjoint path covers with path length constraints in restricted hypercube-like graphs
• Characterization of interval graphs that are unpaired 2-disjoint path coverable
• Many-to-many two-disjoint path covers in cylindrical and toroidal grids
• Ore-type degree conditions for disjoint path covers in simple graphs
• Many-to-many two-disjoint path covers in restricted hypercube-like graphs
• Single-source three-disjoint path covers in cubes of connected graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Fault-tolerant embedding of starlike trees into restricted hypercube-like graphs
• Paired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge Faults
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• On characterizing radio \(k\)-coloring problem by path covering problem
• Hole: An Emerging Character in the Story of Radio k-Coloring Problem
• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Minimal controllability of conjunctive Boolean networks is NP-complete
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• Parameterizing path partitions
• On legal path problems in digraphs
• Parameterizing path partitions
• Degree sequence conditions for a graph to be disjoint path coverable
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Torus-like graphs and their paired many-to-many disjoint path covers
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• Path covering problems and testing of printed circuits
• One-to-one disjoint path covers in digraphs
• Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest
• Distance-based covering problems for graphs of given cyclomatic number

This page was built for publication: On Path Cover Problems in Digraphs and Applications to Program Testing

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