Reload cost problems: Minimum diameter spanning tree

DOI10.1016/S0166-218X(00)00392-9MaRDI QIDQ5948962zbMATH OpenOpenAlexFDO

Authors H.-C. Wirth, Jan Steffan

Publication date 30 July 2002

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

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00392-9

zbMATH Keywords

diameteredge-weighted graphexact algorithmoptimization problemspanning treetransportation problems

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Traffic problems in operations research (90B20)

Review text

This paper is concerned with a special optimization problem on an edge-colored graph. Given a reload cost function on pairs of colours, reload cost distance is defined for a path of the graph. The problem is to find a spanning tree of the graph such that the path with maximal reload cost distance (diameter) is minimized on all spanning trees.NEWLINENEWLINENEWLINEComputational complexity results are presented for the general problem case with cost function satisfying the triangle inequality and for graphs of degree 5. The authors also present an exact algorithm for graphs with maximum degree 3 and triangle inequality condition. The algorithm is based on the idea to map the graph with reload costs to an equivalent edge-weighted graph and then to use the known algorithms for minimum diameter spanning trees.NEWLINENEWLINENEWLINEOverall, this paper contains valuable original results which probably have not been presented in literature so far.

Recommendations

• The complexity of a minimum reload cost diameter problem
• scientific article; zbMATH DE number 1420900
• The Minimum Reload s-t Path/Trail/Walk Problems
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• On the complexity of constructing minimum changeover cost arborescences

Cites work

• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1420900 (Why is no real title available?)
• On the minimum diameter spanning tree problem
• On the minimum label spanning tree problem
• The complexity of designing a network with minimum diameter
• The minimum labeling spanning trees

Cited in

(21)

• The complexity of a minimum reload cost diameter problem
• A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
• The quadratic cycle cover problem: special cases and efficient bounds
• On the complexity of constructing minimum changeover cost arborescences
• Alternating-pancyclism in 2-edge-colored graphs
• On minimum reload cost cycle cover
• Reload cost trees and network design
• On minimum reload cost paths, tours, and flows
• On solving the quadratic shortest path problem
• The Minimum Reload s-t Path/Trail/Walk Problems
• scientific article; zbMATH DE number 1420900 (Why is no real title available?)
• On minimum reload cost cycle cover
• SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• Minimum <scp>color‐degree</scp> perfect b‐matchings
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization
• On penalized reload cost path, walk, tour and maximum flow: hardness and approximation
• Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs
• The minimum reload \(s-t\) path, trail and walk problems

This page was built for publication: Reload cost problems: Minimum diameter spanning tree

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