Nontrivial path covers of graphs: existence, minimization and maximization
DOI10.1007/S10878-019-00488-WzbMATH Open1434.90209OpenAlexW2990181100WikidataQ122111967 ScholiaQ122111967MaRDI QIDQ2292153FDOQ2292153
Renzo Gómez, Yoshiko Wakabayashi
Publication date: 3 February 2020
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-019-00488-w
Recommendations
- Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
- Minimum \(k\)-path vertex cover
- Complexity of the maximum \(k\)-path vertex cover problem
- The weighted \(k\)-path vertex cover problem on series-parallel graphs
- A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Matching theory
- Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Title not available (Why is that?)
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Linear algorithm for optimal path cover problem on interval graphs
- Relating path coverings to vertex labellings with a condition at distance two
- HAMILTONian circuits in chordal bipartite graphs
- The Traveling Salesman Problem with Distances One and Two
- Paths, Stars and the Number Three
- An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
- Coverings of Bipartite Graphs
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Matchings, path covers and domination
- Subgraphs with prescribed valencies
- Optimal covering of cacti by vertex-disjoint paths
- An algorithmic proof of Tutte's f-factor theorem
- [a,b]-factors of graphs
- An extension of Tutte's 1-factor theorem
- A simple existence criterion for \((g<f)\)-factors
- Covering 2‐connected 3‐regular graphs with disjoint paths
- Title not available (Why is that?)
- Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
- A note on the path cover number of regular graphs
Cited In (11)
- The existence of path-factor covered graphs
- Path coverings of graphs and height characteristics of matrices
- Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
- Approximation algorithms for covering vertices by long paths
- A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs
- Maximum nullity of outerplanar graphs and the path cover number
- Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
- An approximation algorithm for covering vertices by \(4^+\)-paths
- An optimal path cover algorithm for cographs
- Path cover problems with length cost
- Path cover problems with length cost
This page was built for publication: Nontrivial path covers of graphs: existence, minimization and maximization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292153)
