## Abstract

In the QoS shortest path problem, we want to find a path connecting two given vertices u and v to minimize path cost subject to the constraint that the path weight is no greater than a given bound. In the QoS minimum spanning tree problem, we want to find a spanning tree to minimize tree cost subject to the constraint that the tree weight is no greater than a given bound. Both problems are NP-hard and have important applications in computer and communication networks. We present simple but effective primal-dual algorithms for computing approximate solutions for both problems. Computational results show that our algorithm find optimal solutions in more than 80% of the cases and find close to optimal solutions in all other cases, while using much less time.

Original language | English (US) |
---|---|

Pages (from-to) | 271-277 |

Number of pages | 7 |

Journal | IEEE International Performance, Computing and Communications Conference, Proceedings |

State | Published - Jan 1 2000 |

Externally published | Yes |

Event | IEEE International Performance, Computing, and Communications Conference (IPCCC 2000) - Phoenix, AZ, USA Duration: Feb 20 2000 → Feb 22 2000 |

## ASJC Scopus subject areas

- Media Technology