The subdivision-constrained routing requests problem

DOI10.1007/s10878-012-9497-4zbMath1286.90156OpenAlexW2069277305MaRDI QIDQ2436672

Junran Lichen, Jianping Li, Weidong Li

Publication date: 25 February 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9497-4

zbMATH Keywords

approximation algorithmsubdivisionNP-hardnessinapproximabilitystrongly polynomial-time algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• The subdivision-constrained minimum spanning tree problem
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology
• An improved FPTAS for Restricted Shortest Path.
• Design networks with bounded pairwise distance
• A threshold of ln n for approximating set cover
• Set connectivity problems in undirected graphs and the directed steiner network problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation Algorithms for Directed Steiner Problems
• The network inhibition problem
• Approximations for Steiner trees with minimum number of Steiner points

This page was built for publication: The subdivision-constrained routing requests problem