## Abstract

We consider the bicriteria optimization problem of computing a shallow-light tree. Given a directed graph with two unrelated cost functions defined on its edges: weight and length, and a designated root vertex, the goal is to find a minimum weight spanning tree such that the path lengths from its root to the rest of the vertices are bounded. This problem has several applications in network and VLSI design, and information retrieval. We give a polynomial time algorithm for finding a spanning tree whose weight is O(log |V|) times the weight of an optimal shallow-light tree, where the path lengths from the root to the rest of the vertices are at most twice the given bounds. We extend our technique to handle two variants of the problem: one in which the length bound is given on the average length of a path from the root to a vertex, and another tricriteria budgeted version. Our paper provides the first non-trivial approximation factors for directed graphs, and improves on previous results for undirected graphs.

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

Title of host publication | Annual Symposium on Foundations of Computer Science - Proceedings |

Publisher | IEEE Comp Soc |

Pages | 536-541 |

Number of pages | 6 |

ISBN (Print) | 0818681977 |

DOIs | |

State | Published - 1997 |

Externally published | Yes |

Event | Proceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA Duration: Oct 20 1997 → Oct 22 1997 |

### Conference

Conference | Proceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science |
---|---|

City | Miami Beach, FL, USA |

Period | 10/20/97 → 10/22/97 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture