A subexponential algorithm for the coloured tree partition problem

DOI10.1016/J.DAM.2007.02.001MaRDI QIDQ2370434zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Heuristic algorithms for the maximum colorful subtree problem
• An exact algorithm for the partition coloring problem
• scientific article; zbMATH DE number 2089998
• A branch-and-cut algorithm for partition coloring
• A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
• scientific article; zbMATH DE number 1262791
• Algorithms for finding f-colorings of partial k-trees
• Approximation Algorithms for Path Coloring in Trees
• Colorings of trees with linear, intermediate and exponential subball complexity
• A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree

Cites work

• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• A Shifting Algorithm for Min-Max Tree Partitioning
• Aspects of edge list-colourings
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• Introduction to algorithms
• Maximal circuits of graphs. I
• Multicriterial graph problems with MAXMIN criterion
• On the complexity of graph tree partition problems.
• Shifting algorithms for tree partitioning with general weighting functions
• Tree partitioning under constraints. -- Clustering for vehicle routing problems

Cited in

(1)

• Colored-independence (mostly) on trees

Describes a project that uses

Uses Software

• XRules

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370434)