Wire routing and satisfiability planning

Esra Erdem, Vladimir Lifschitz, Martin D. F. Wong

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

13 Citations (Scopus)


Wire routing is the problem of determining the physical lo- cations of all the wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial opti- mization problem. We present a new approach to wire routing that uses action languages and satisfiability planning. Its idea is to think of each path as the trajectory of a robot, and to understand a routing problem as the problem of planning the actions of several robots whose paths are required to be disjoint. The new method differs from the algorithms implemented in the existing routing systems in that it always correctly determines whether a given problem is solvable, and it produces a solu- tion whenever one exists.

Original languageEnglish
Title of host publicationComputational Logic - CL 2000
Subtitle of host publicationFirst International Conference London, UK, July 24–28, 2000 Proceedings
EditorsJohn Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu Lau, Catuscia Palamidessi, Luís Moniz Pereira, Yehoshua Sagiv, Peter J. Stuckey
Place of PublicationBerlin
PublisherSpringer Verlag
Number of pages15
ISBN (Electronic)9783540449577
ISBN (Print)9783540677970
Publication statusPublished - 24 Jul 2000
Event1st International Conference on Computational Logic, CL 2000 - London, United Kingdom
Duration: 24 Jul 200028 Jul 2000

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameLecture Notes in Artificial Intelligence
ISSN (Print)2945-9133
ISSN (Electronic)2945-9141
NameCL: International Conference on Computational Logic Proceedings


Conference1st International Conference on Computational Logic, CL 2000
Country/TerritoryUnited Kingdom
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Very Large Scale Integrate
  • Action Language
  • Default Theory
  • Plan Fact
  • Circuit Component


Dive into the research topics of 'Wire routing and satisfiability planning'. Together they form a unique fingerprint.

Cite this