## Abstract

The routing problem in VLSI-layout can be modeled as a problem of packing node-disjoint Steiner trees in a graph. The problem is as follows: Given an undirected network G = (V, E) and a net list Ψ = {N_{iy} i = 1,…, r}, a family Г_{G} — {T_{Ni} = (V_{Ni}, E_{Ni}), i = 1,…, r} is a node-disjoint family of Steiner trees spanning Ψ if T_{Ni} is a Steiner tree spanning N_{i} for i = 1,…, r and V_{Ni} ∩V_{Nj} = for i # j. The edge-disjoint version of this problem is known to be NP-hard for series-parallel graphs (see Richey and Parker [5]). In this paper we give a O(n^{5}) algorithm for finding a minimum-cost node-disjoint family of Steiner trees in series-parallel networks. Our algorithm can be extended to &-trees and is polynomial for fixed k.

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

Pages (from-to) | 53-57 |

Number of pages | 5 |

Journal | VLSI Design |

Volume | 4 |

Issue number | 1 |

DOIs | |

State | Published - 1996 |

Externally published | Yes |

## Keywords

- Network Design
- Series-Parallel
- Steiner Trees
- VLSI

## ASJC Scopus subject areas

- Hardware and Architecture
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering