Article ID: | iaor20121052 |

Volume: | 31 |

Issue: | 1 |

Start Page Number: | 58 |

End Page Number: | 78 |

Publication Date: | Sep 2001 |

Journal: | Algorithmica |

Authors: | Ravi R, Rosenkrantz D J, Ravi S S, Marathe M V, Hunt III H B |

Keywords: | combinatorial optimization, programming: multiple criteria |

Abstract:

We study network‐design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree‐constrained node‐weighted Steiner tree problem: We are given an undirected graph