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

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

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

(25)

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

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)