Technique d'optimisation par ordinateur des couples de noeuds dans un graphe donne de couplages possibles

Verfahren zur ermittlung von optimierten kopplungen von knoten in einem vorgegebenen graph möglicher kopplungen, durch einen rechner

Computer-aided optimization of node couples in a given graph showing coupling possibilities

  • Inventors:
  • Assignees:
  • Publication Date: May 07, 1998
  • Publication Number: WO-9812652-A3

Abstract

En utilisant des fonctions label de noeuds plutôt que les labels eux-mêmes dans une procédure visant à résoudre le problème de l''arbre de Steiner', par exemple par une procédé visant à déterminer le trajet le plus court dans un graphe, on peut tenir compte des restrictions lors la détermination de trajets moins coûteux, qu'il s'agisse notamment de restrictions de longueur ou de base de temps.
Durch Verwendung von Knotenlabelfunktionen anstelle von Knotenlabeln in einem Verfahren zur Lösung eines Steiner-Baum-Problems, beispielsweise durch ein Verfahren zur Ermittlung kürzester Pfade in einem Graphen, wird es möglich, Restriktionen während der Ermittlung kostengünstigster Pfade zu berücksichtigen. Restriktionen können beispielsweise Längenrestriktionen oder Timingrestriktionen sein.
Using node label functions instead of labels themselves in a procedure aiming at solving the so-called Steiner-tree problem, for example by a process intended to identify the shorter path in a graph, allows for restrictions, either length or time-frame restrictions, to be taken into account when determining cheaper paths.

Claims

Description

Topics

Download Full PDF Version (Non-Commercial Use)

Patent Citations (0)

    Publication numberPublication dateAssigneeTitle

NO-Patent Citations (4)

    Title
    CONG J ET AL: "PROVABLY GOOD ALGORITHMS FOR PERFORMANCE-DRIVEN GLOBAL ROUTING", PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, SAN DIEGO, MAY 10 - 13, 1992, vol. 5 OF 6, 10 May 1992 (1992-05-10), INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, pages 2240 - 2243, XP000338436
    DONGSHENG ET AL: "performance-driven interconnect global routing", IEEE PROCEEDINGS OF THE SIXTH GREAT LAKES SYMPOSIUM ON VLSI, 22 March 1996 (1996-03-22) - 23 March 1996 (1996-03-23), US, pages 132 - 136, XP002057848
    NOVAK R ET AL: "DISTRIBUTION OF CONSTRAINED STEINER TREE COMPUTATION IN SHORTEST-DELAY NETWORKS", MELECON '96. 8TH. MEDITERRANEAN ELECTROTECHNICAL CONFERENCE INDUSTRIAL APPLICATIONS IN POWER SYSTEMS, COMPUTER SCIENCE AND TELECOMMUNICATIONS, BARI, IT., MAY 13 - 16, 1996, vol. VOL. 2, no. CONF. 8, 13 May 1996 (1996-05-13), DE SARIO M;MALONE B; PUGLIESE P; SAVINO M (EDS ), pages 959 - 962, XP000699429
    ROSENWEIN ET AL: "a constrained steiner tree problem", EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 81, no. 2, March 1995 (1995-03-01), NETHERLANDS, pages 430 - 439, XP002057847

Cited By (0)

    Publication numberPublication dateAssigneeTitle