Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks

Sunil Chopra, Kalyan T. Talluri

Research output: Contribution to journalArticlepeer-review

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 Ψ = {Niy i = 1,…, r}, a family ГG — {TNi = (VNi, ENi), i = 1,…, r} is a node-disjoint family of Steiner trees spanning Ψ if TNi is a Steiner tree spanning Ni for i = 1,…, r and VNi ∩VNj = 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(n5) 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 languageEnglish (US)
Pages (from-to)53-57
Number of pages5
JournalVLSI Design
Volume4
Issue number1
DOIs
StatePublished - 1996

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

Fingerprint Dive into the research topics of 'Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks'. Together they form a unique fingerprint.

Cite this