Optimal covering of cacti by vertex-disjoint paths
From MaRDI portal
Publication:1178689
DOI10.1016/0304-3975(91)90159-YzbMath0741.68082OpenAlexW2075920437MaRDI QIDQ1178689
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90159-y
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
On the \(k\)-path cover problem for cacti, Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow, Hole: An Emerging Character in the Story of Radio k-Coloring Problem, Unnamed Item, Fast-mixed searching and related problems on graphs, A survey of parameterized algorithms and the complexity of edge modification, Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor, Path covering number and \(L(2,1)\)-labeling number of graphs, Finding a minimum path cover of a distance-hereditary graph in polynomial time, On characterizing radio \(k\)-coloring problem by path covering problem, Efficient algorithm for the vertex cover \(P_k\) problem on cacti, Complexity and inapproximability results for the power edge set problem, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Nontrivial path covers of graphs: existence, minimization and maximization, Optimal path cover problem on block graphs and bipartite permutation graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Solving the path cover problem on circular-arc graphs by using an approximation algorithm
Uses Software
Cites Work
