The P k Partition Problem and Related Problems in Bipartite Graphs

DOI10.1007/978-3-540-69507-3_36MaRDI QIDQ5448792zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot, Sophie Toulouse

Publication date 7 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69507-3_36

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• The path partition problem and related problems in bipartite graphs
• On the \(k\)-path partition of graphs.
• An improved approximation algorithm for the minimum 3-path partition problem
• Partitioning a bipartite graph into vertex-disjoint paths.
• On the k-path partition problem in cographs

Cited in

(26)

• The \(k\)-partitioning problem
• On the \(k\)-path partition of graphs.
• Improved approximation algorithms for weighted 2-path partitions
• A boundary class for the k-path partition problem
• Metabolic networks are NP-hard to reconstruct
• A local search algorithm for binary maximum 2-path partitioning
• Efficient algorithms for path partitions
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• On the Kegel-Wielandt -problem for binary partitions
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• An improved approximation algorithm for the minimum 3-path partition problem
• Packing paths: recycling saves time
• The path partition problem and related problems in bipartite graphs
• Approximating element-weighted vertex deletion problems for the complete k-partite property
• Improved approximation algorithms for weighted 2-path partitions
• Problème de la bipartition minimale d'un graphe
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Relaxed complete partitions: an error-correcting Bachet's problem
• On Approximating the Maximum Simple Sharing Problem
• On a bipartition problem of Bollobás and Scott
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• A parameterized perspective on packing paths of length two
• Approximation results for the weighted \(P_4\) partition problem
• Approximability results for the maximum and minimum maximal induced matching problems
• Partition into cliques for cubic graphs: Planar case, complexity and approximation

This page was built for publication: The P k Partition Problem and Related Problems in Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448792)