The P k Partition Problem and Related Problems in Bipartite Graphs

DOI10.1007/978-3-540-69507-3_36zbMath1130.68081OpenAlexW1558426225MaRDI QIDQ5448792

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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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) Approximation algorithms (68W25)

Related Items (7)

On the computational complexity of the Helly number in the \(P_3\) and related convexities ⋮ A parameterized perspective on packing paths of length two ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Packing paths: recycling saves time ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Metabolic networks are NP-hard to reconstruct

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