Balanced Partition of Minimum Spanning Trees

Summary, in English

To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve "optimally" dividing a task into k smaller tasks. We consider the problem of partitioning a given set S of n points (in the plane) into k subsets, S1,...,Sk that max 1leqslant i leqslant k |MST(Si) | is minimized. A variant of this problem arises in the shipbuilding industry [2].

• Författare: Mattias Andersson; Joachim Gudmundsson; Christos Levcopoulos; Giri Narasimhan
• Avdelning/ar: Computer Science
• Publiceringsår: 2002
• Språk: Engelska
• Sidor: 26-35
• Publikation/Tidskrift/Serie: Computational Science — ICCS 2002 / Lecture notes in computer science
• Volym: 2331
• Länkar: http://dx.doi.org/10.1007/3-540-47789-6_3
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: International Conference on Computational Science
• Conference date: 2002-04-21 - 2002-04-24
• Conference place: Netherlands
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 0302-9743; ISSN: 1611-3349