On uniform \(k\)-partition problems

DOI10.1016/j.dam.2005.02.013zbMath1071.05061OpenAlexW2065074947MaRDI QIDQ2565854

Paolo Dell'Olmo, Pierre Hansen, Stefano Pallottino, Giovanni Storchi

Publication date: 28 September 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.02.013

zbMATH Keywords

algorithmschedulingmatchingpolynomialrouting problems

Mathematics Subject Classification ID

Partitions of sets (05A18) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint, Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint, Optimal matroid partitioning problems, \(k\)-partitioning problems with partition matroid constraint, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selected topics on assignment problems
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Balanced optimization problems
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• Paths with minimum range and ratio of arc lengths
• Time bounds for selection