The P k Partition Problem and Related Problems in Bipartite Graphs
DOI10.1007/978-3-540-69507-3_36zbMATH Open1130.68081OpenAlexW1558426225MaRDI QIDQ5448792FDOQ5448792
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
Recommendations
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)
Cited In (25)
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- Packing paths: recycling saves time
- An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
- 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
- The \(k\)-partitioning problem
- Approximability results for the maximum and minimum maximal induced matching problems
- 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 \(\sigma\)-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)
