Rectilinear Steiner Tree Construction Using Answer Set Programming

Esra Erdem, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

14 Citations (Scopus)


We introduce a new method for Rectilinear Steiner Tree (RST) construction in a graph, using answer set programming. This method provides a formal representation of the problem as a logic program whose answer sets correspond to solutions. The answer sets for a logic program can be computed by special systems called answer set solvers. We describe the method for RST construction in the context of VLSI routing where multiple pins in a given placement of a chip are connected by an RST. Our method is different from the existing methods mainly in three ways. First, it always correctly determines whether a given RST routing problem is solvable, and it always produces a solution if one exists. Second, some enhancements of the basic problem, in which lengths of wires connecting the source pin to sink pins are restricted, can be easily represented by adding some rules. Our method guarantees to find a tree if one exists, even when the total wire length is not minimum. Third, routing problems with the presence of obstacles can be solved. With this approach, we have computed solutions to some RST routing problems using the answer set solver CMODELS.
Original languageEnglish
Title of host publicationLogic Programming
Subtitle of host publication20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings
EditorsBart Demoen, Vladimir Lifschitz
Place of PublicationGermany
PublisherSpringer Berlin Heidelberg
Number of pages14
ISBN (Electronic)9783540277750
ISBN (Print)9783540226710
Publication statusPublished - 24 Aug 2004
Event20th International Conference on Logic Programming, ICLP 2004 - Palais du Grand Large, Saint-Malo, France
Duration: 6 Sept 200410 Sept 2004 (Conference website) (Conference programme) (Conference proceedings)

Publication series

NameLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Logic Programming, ICLP 2004
Internet address

User-Defined Keywords

  • Logic Program
  • Steiner Tree
  • Steiner Tree Problem
  • Unit Segment
  • Vertical Line Segment


Dive into the research topics of 'Rectilinear Steiner Tree Construction Using Answer Set Programming'. Together they form a unique fingerprint.

Cite this