zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing. (English) Zbl 1176.90612

Summary: We generalize Dijkstra’s algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.

As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.

MSC:
90C35Programming involving graphs or networks
90B10Network models, deterministic (optimization)
90B20Traffic problems
References:
[1]Albrecht, C.: Global routing by new approximation algorithms for multicommodity flow, IEEE transactions on computer aided design of integrated circuits and systems 20, 622-632 (2001)
[2]Bast, H.; Funke, S.; Matijevic, D.; Sanders, P.; Schultes, D.: In transit to constant time shortest-path queries in road networks, (2007)
[3]S. Batterywala, N. Shenoy, W. Nicholls, H. Zhou, Track assignment: A desirable intermediate step between global routing and detailed routing, in: Proc. IEEE International Conference on Computer Aided Design, 2002, pp. 59 – 66
[4]R. Bauer, D. Delling, SHARC: Fast and robust unidirectional routing, in: Proc. 10th International Workshop on Algorithm Engineering and Experiments (ALENEX’08), pp. 13 – 26
[5]R. Bauer, D. Delling, D. Wagner, Experimental study on speed-up techniques for timetable information systems, in: Proc. 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007)
[6]Cherkassky, B. V.; Goldberg, A. V.; Radzik, T.: Shortest paths algorithms: theory and experimental evaluation, Math. prog. 73, 129-174 (1996) · Zbl 0853.90111 · doi:10.1007/BF02592101
[7]Cong, J.; Fang, J.; Khoo, K.: DUNE — A multilayer gridless routing system, IEEE transactions on computer-aided design of integrated circuits and systems 20, 633-647 (2001)
[8]Cong, J.; Fang, J.; Xie, M.; Zhang, Y.: Mars — A multilevel full-chip gridless routing system, IEEE transactions on computer-aided design of integrated circuits and systems 24, 382-394 (2005)
[9]Demetrescu, C.; Goldberg, A. V.; Johnson, D. S.: Implementation challenge for shortest paths, Encyclopedia of algorithms, 395-398 (2008)
[10]Dijkstra, E. W.: A note on two problems in connexion with graphs, Numerische Mathematik 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[11]Doran, J.: An approach to automatic problem-solving, Machine intelligence 1, 105-127 (1967)
[12]Fredman, M. L.; Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization problems, Journal of the ACM 34, 596-615 (1987)
[13]Gallo, G.; Pallottino, S.: Shortest paths algorithms, Annals of operations research 13, 3-79 (1988)
[14]Goldberg, A. V.: A simple shortest path algorithm with linear average time, Lecture notes in computer science (LNCS) 2161, 230-241 (2001) · Zbl 1007.05088 · doi:http://link.springer.de/link/service/series/0558/bibs/2161/21610230
[15]A.V. Goldberg, C. Harrelson, Computing the shortest path: A* search meets graph theory, in: Proc. 16th ACM – SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 156 – 165
[16]Hart, P. E.; Nilsson, N. J.; Raphael, B.: A formal basis for the heuristic determination of minimum cost paths in graphs, IEEE transactions on systems science and cybernetics, SSC 4, 100-107 (1968)
[17]A. Hetzel, A sequential detailed router for huge grid graphs, in: Proc. Design, Automation and Test in Europe (DATE 1998), pp. 332 – 339
[18]W. Heyns, W. Sansen, H. Beke, A line-expansion algorithm for the general routing problem with a guaranteed solution, in: Proc. 17th Design Automation Conference, 1980, pp. 243 – 249
[19]D.W. Hightower, A solution to line-routing problems on the continuous plane, in: Proc. 6th Design Automation Conference, 1969, pp. 1 – 24
[20]Hoel, J. H.: Some variations of Lee’s algorithm, IEEE transactions on computers 25, 19-24 (1976) · Zbl 0329.68040 · doi:10.1109/TC.1976.5009200
[21]Holzer, M.; Schulz, F.; Wagner, D.; Willhalm, T.: Combining speed-up techniques for shortest-path computations, Journal of experimental algorithmics (JEA) 10, 1-18 (2005)
[22]Hu, J.; Sapatnekar, S. S.: A survey on multi-net global routing for integrated circuits, Integration the VLSI journal 31, 1-49 (2001) · Zbl 0995.68197 · doi:10.1016/S0167-9260(01)00020-7
[23]J. Humpola, Schneller Algorithmus für kürzeste Wege in irregulären Gittergraphen, Diploma Thesis, University of Bonn, 2009
[24]Klunder, G. A.; Post, H. N.: The shortest path problem on large-scale real-road networks, Networks 48, 182-194 (2006) · Zbl 1148.90346 · doi:10.1002/net.20131
[25]Köhler, E.; Möhring, R. H.; Schilling, H.: Acceleration of shortest path and constrained shortest path computation, Lecture notes in computer science (LNCS) 3503, 126-138 (2005) · Zbl 1121.90413 · doi:10.1007/b136461
[26]Korte, B.; Rautenbach, D.; Vygen, J.: Bonntools: mathematical innovation for layout and timing closure of systems on a chip, Proc. of the IEEE 95, 555-572 (2007)
[27]Lauther, U.: An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background, , 219-230 (2004)
[28]Lee, C. Y.: An algorithm for path connections and its application, IRE transactions on electronic computing 10, 346-365 (1961)
[29]Li, Y. -L.; Chen, H. -Y.; Lin, C. -T.: NEMO: A new implicit-connection-graph-based gridless router with multilayer planes and pseudo tile propagation, IEEE transactions on computer-aided design of integrated circuits and systems 26, 705-718 (2007)
[30]Margarino, A.; Romano, A.; De Gloria, A.; Curatelli, Francesco; Antognetti, P.: A tile-expansion router, IEEE transactions on CAD of integrated circuits and systems 6, 507-517 (1987)
[31]U. Meyer, Single-source shortest paths on arbitrary directed graphs in linear average time, in: Proc. 12th ACM – SIAM Symposium on Discrete Algorithms (SODA), 2001, pp. 797 – 806 · Zbl 0988.05088
[32]Möhring, R. H.; Schilling, H.; Schütz, B.; Wagner, D.; Willhalm, T.: Partitioning graphs to speed up dijkstra’s algorithm, Lecture notes in computer science (LNCS) 3503, 189-202 (2005) · Zbl 1121.68356 · doi:10.1007/b136461
[33]Pohl, I.: Bi-directional search, Machine intelligence 6, 124-140 (1971) · Zbl 0263.68021
[34]Rubin, F.: The Lee path connection algorithm, IEEE transactions on computers 23, 907-914 (1974) · Zbl 0291.90071 · doi:10.1109/T-C.1974.224054
[35]Sanders, P.; Schultes, D.: Highway hierarchies hasten exact shortest path queries, Lecture notes in computer science (LNCS) 3669, 568-579 (2005) · Zbl 1162.68505 · doi:10.1007/11561071
[36]Schulz, F.; Wagner, D.; Weihe, K.: Using multi-level graphs for timetable information, Lecture notes in computer science (LNCS) 2409, 43-59 (2002)
[37]Sedgewick, R.; Vitter, J.: Shortest paths in Euclidean graphs, Algorithmica 1, 31-48 (1986) · Zbl 0611.68044 · doi:10.1007/BF01840435
[38]Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM 46, 362-394 (1999) · Zbl 1065.68597 · doi:10.1145/316542.316548
[39]Vygen, J.: Near-optimum global routing with coupling, delay bounds, and power consumption, Lecture notes in computer science (LNCS) 3064, 308-324 (2004) · Zbl 1092.68002 · doi:10.1007/b97946
[40]Wagner, D.; Willhalm, T.: Geometric speed-up techniques for finding shortest paths in large sparse graphs, Lecture notes in computer science (LNCS) 2832, 776-787 (2003)
[41]Wagner, D.; Willhalm, T.: Speed-up techniques shortest path computations, Lecture notes in computer science (LNCS) 4393, 23-36 (2007) · Zbl 1186.68594 · doi:10.1007/978-3-540-70918-3_3
[42]Xing, Z.; Kao, R.: Shortest path search using tiles and piecewise linear cost propagation, IEEE transactions on CAD of integrated circuits and systems 21, 145-158 (2002)