On Path Cover Problems in Digraphs and Applications to Program Testing
From MaRDI portal
Publication:4199539
DOI10.1109/TSE.1979.234213zbMath0412.68052OpenAlexW2057052228MaRDI QIDQ4199539
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
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) Directed graphs (digraphs), tournaments (05C20)
Related Items (36)
Algorithms for finding disjoint path covers in unit interval graphs ⋮ Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ Paired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ Minimal controllability of conjunctive Boolean networks is NP-complete ⋮ Path covering problems and testing of printed circuits ⋮ Hole: An Emerging Character in the Story of Radio k-Coloring Problem ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Parameterizing path partitions ⋮ Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest ⋮ Ore-type degree conditions for disjoint path covers in simple graphs ⋮ Paired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge Faults ⋮ One-to-one disjoint path covers in digraphs ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ Degree sequence conditions for a graph to be disjoint path coverable ⋮ One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes ⋮ Many-to-many two-disjoint path covers in restricted hypercube-like graphs ⋮ Single-source three-disjoint path covers in cubes of connected graphs ⋮ Torus-like graphs and their paired many-to-many disjoint path covers ⋮ Path covering number and \(L(2,1)\)-labeling number of graphs ⋮ How to guard a graph? ⋮ One-to-one disjoint path covers on alternating group graphs ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ On characterizing radio \(k\)-coloring problem by path covering problem ⋮ Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks ⋮ Fault-tolerant embedding of starlike trees into restricted hypercube-like graphs ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ On legal path problems in digraphs ⋮ Many-to-many two-disjoint path covers in cylindrical and toroidal grids ⋮ On the computational complexity of path cover problems ⋮ The unpaired many-to-many \(k\)-disjoint paths in bipartite hypercube-like networks
This page was built for publication: On Path Cover Problems in Digraphs and Applications to Program Testing
