Delay-constrained minimum shortest path trees and related problems

DOI10.1016/J.TCS.2022.11.014MaRDI QIDQ5925589zbMATH OpenOpenAlexFDO

Authors Junran Lichen, Lijian Cai, Jianping Li, Suding Liu, Pengxiang Pan, Wencheng Wang

Publication date 4 January 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.11.014

zbMATH Keywords

combinatorial optimizationcomplexitydelay-constrained minimum shortest path treesdiameter-constrained minimum shortest path treesexact algorithms in polynomial time

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• Approximation algorithms for quickest spanning tree problems
• Algorithms – ESA 2004
• SOFSEM 2005: Theory and Practice of Computer Science
• Random-tree diameter and the diameter-constrained MST

Cites work

• A hybrid heuristic for the diameter constrained minimum spanning tree problem
• A note on two problems in connexion with graphs
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Approximating the weight of shallow Steiner trees
• Bounded-diameter minimum-cost graph problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Delay-constrained minimum shortest path trees and related problems
• Discrete-variable extremum problems
• Finding Minimum Spanning Trees
• Geometric minimum diameter minimum cost spanning tree problem
• Graph theory
• Greedy heuristics for the bounded diameter minimum spanning tree problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• Minimum Diameter Spanning Trees and Related Problems
• On the minimum diameter spanning tree problem
• Optimum branchings
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• The absolute center of a network
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cited in

(2)

• Delay-related secondary objectives for rectilinear Steiner minimum trees.
• Delay-constrained shortest paths: approximation algorithms and second-order cone models

This page was built for publication: Delay-constrained minimum shortest path trees and related problems

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