On the complexity of quality of service routing

DOI10.1016/S0020-0190(98)00206-3MaRDI QIDQ294629zbMATH OpenFDO

Authors Zheng Wang

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098002063?np=y

zbMATH Keywords

shortest pathroutingcomputational complexity: NP-completenessmultiple constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1969707
• QOS routing algorithms for anycast services
• Quality-of-Service routing with path information aggregation
• scientific article; zbMATH DE number 1955773
• Dynamic online QoS routing schemes: Performance and bounds
• Packet Routing: Complexity and Algorithms
• Optimal choice of the capacities of telecommunication networks to provide QoS-routing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms for finding paths with multiple constraints

Cited in

(16)

• Search space reduction in QoS routing.
• Complexity results on labeled shortest path problems from wireless routing metrics
• scientific article; zbMATH DE number 1969707 (Why is no real title available?)
• Unicast and multicast QoS routing with soft-constraint logic programming
• New Routing Strategies for RSP Problems with Concave Cost
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• Efficient QoS routing.
• Multi-postpath-based lookahead multiconstraint QoS routing
• Precomputation for intra-domain QoS routing
• Dynamic online QoS routing schemes: Performance and bounds
• Packet Routing: Complexity and Algorithms
• Highly responsive and efficient QoS routing using pre- and on-demand computations along with a new normal measure
• A survey on multi-constrained optimal path computation: exact and approximate algorithms
• scientific article; zbMATH DE number 1717140 (Why is no real title available?)
• Sensible decisions based on QoS
• On the Convexity of Feasible QoS Regions

This page was built for publication: On the complexity of quality of service routing

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