A subexponential algorithm for the coloured tree partition problem

DOI10.1016/j.dam.2007.02.001zbMath1120.68110OpenAlexW2117469129MaRDI QIDQ2370434

Roberto Cordone

Publication date: 26 June 2007

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

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

zbMATH Keywords

divide-and-conquertree partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• XRules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• On the complexity of graph tree partition problems.
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Tree partitioning under constraints. -- Clustering for vehicle routing problems
• Shifting algorithms for tree partitioning with general weighting functions
• A Shifting Algorithm for Min-Max Tree Partitioning
• Maximal circuits of graphs. I
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Aspects of edge list-colourings

This page was built for publication: A subexponential algorithm for the coloured tree partition problem