Nontrivial path covers of graphs: existence, minimization and maximization

DOI10.1007/S10878-019-00488-WMaRDI QIDQ2292153zbMATH OpenOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

bounded treewidthcovering\([1,2\)-factor]max path covermin path cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

Cites work

• scientific article; zbMATH DE number 1117461 (Why is no real title available?)
• A note on the path cover number of regular graphs
• A simple existence criterion for \((g<f)\)-factors
• An algorithmic proof of Tutte's f-factor theorem
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• An extension of Tutte's 1-factor theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Covering 2-connected 3-regular graphs with disjoint paths
• Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
• Coverings of Bipartite Graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• HAMILTONian circuits in chordal bipartite graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Linear algorithm for optimal path cover problem on interval graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Matching theory
• Matchings, path covers and domination
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Optimal covering of cacti by vertex-disjoint paths
• Paths, Stars and the Number Three
• Relating path coverings to vertex labellings with a condition at distance two
• Subgraphs with prescribed valencies
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Traveling Salesman Problem with Distances One and Two
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• [a,b]-factors of graphs

Cited in

(12)

• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• 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
• An approximation algorithm for covering vertices by \(4^+\)-paths
• Path cover problems with length cost
• The existence of path-factor covered graphs
• Path coverings of graphs and height characteristics of matrices
• Covering pairs in directed acyclic graphs
• Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
• Path cover problems with length cost
• An optimal path cover algorithm for cographs
• Approximation algorithms for covering vertices by long paths

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)