On the complexity of graph tree partition problems.
From MaRDI portal
Publication:1421460
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)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
A subexponential algorithm for the coloured tree partition problem ⋮ \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem ⋮ Optimizing wind farm cable routing considering power losses ⋮ Minmax Tree Cover in the Euclidean Space ⋮ Solving the 2-rooted mini-max spanning forest problem by branch-and-bound ⋮ Approximation algorithms for the maximally balanced connected graph tripartition problem ⋮ A class of heuristics for the constrained forest problem ⋮ Another greedy heuristic 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
This page was built for publication: On the complexity of graph tree partition problems.
