On the complexity of graph tree partition problems.

DOI10.1016/S0166-218X(03)00340-8zbMath1074.68043MaRDI QIDQ1421460

Roberto Cordone, Francesco Maffioli

Publication date: 26 January 2004

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

zbMATH Keywords

Computational complexity; Greedy algorithm; Tree partition

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Minmax Tree Cover in the Euclidean Space, Another greedy heuristic for the constrained forest problem, Solving the 2-rooted mini-max spanning forest problem by branch-and-bound, \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem, A subexponential algorithm for the coloured tree partition problem, A class of heuristics for the constrained forest problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Approximation algorithms for minimum tree partition
• A heuristic algorithm for the mini-max spanning forest problem
• A branch-and-bound algorithm for the mini-max spanning forest problem
• A greedy heuristic for a minimum-weight forest problem
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• Balanced spanning forests and trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The complexity of the capacitated tree problem
• Approximation Algorithms for Min–Max Tree Partition
• A General Approximation Technique for Constrained Forest Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs