The path partition problem and related problems in bipartite graphs

DOI10.1016/j.orl.2006.12.004zbMath1129.05034OpenAlexW2074198833MaRDI QIDQ2465958

Sophie Toulouse, Jérôme Monnot

Publication date: 11 January 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2006.12.004

zbMATH Keywords

bipartite graphsapproximation algorithmsAPX-hardnesspath partitionpath packing\(P_k\)-partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Path cover problems with length cost ⋮ Induced star partition of graphs ⋮ Parameterizing path partitions ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Geodesic packing in graphs ⋮ Packing 2- and 3-stars into cubic graphs ⋮ Approximation algorithms for the directed path partition problems ⋮ Edge deletion to tree-like graph classes ⋮ Star covers and star partitions of double-split graphs ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem ⋮ Packing bipartite graphs with covers of complete bipartite graphs ⋮ On upper bounds for parameters related to the construction of special maximum matchings ⋮ Blockers for the stability number and the chromatic number ⋮ Star Partitions of Perfect Graphs ⋮ Heuristic approaches for the optimal wiring in large scale robotic skin design ⋮ Complexity and approximation of the constrained forest problem ⋮ Path cover problems with length cost ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ A boundary class for the \(k\)-path partition problem ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ On the isometric path partition problem ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem ⋮ Network-Based Vertex Dissolution ⋮ Parameterized complexity of \((A,\ell)\)-path packing ⋮ A \(5k\)-vertex kernel for \(P_2\)-packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum packing of 3-edge paths
• Matching theory
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• The hardness of approximation: Gap location
• \(k\)-path partitions in trees
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• On the \(k\)-path partition of graphs.
• An approximation algorithm for maximum triangle packing
• On Local Search for Weighted k-Set Packing
• Planar 3DM is NP-complete
• Path factors of bipartite graphs
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• On the completeness of a generalized matching problem

This page was built for publication: The path partition problem and related problems in bipartite graphs