biblio.bib

   1 @inproceedings{ bender00lca,
   2     author = "Michael A. Bender and Martin Farach-Colton",
   3     title = "The {LCA} Problem Revisited",
   4     booktitle = "Latin American Theoretical {INformatics}",
   5     pages = "88-94",
   6     year = "2000",
   7     url = "citeseer.ist.psu.edu/bender00lca.html" }
   8
   9 @inproceedings{ frederickson91ambivalent,
  10     author = "Greg N. Frederickson",
  11     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
  12     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
  13     pages = "632-641",
  14     year = "1991",
  15     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
  16
  17 @article{ tarjan:setunion,
  18  author = {Robert E. Tarjan and Jan van Leeuwen},
  19  title = {Worst-case Analysis of Set Union Algorithms},
  20  journal = {J. ACM},
  21  volume = {31},
  22  number = {2},
  23  year = {1984},
  24  issn = {0004-5411},
  25  pages = {245--281},
  26  doi = {http://doi.acm.org/10.1145/62.2160},
  27  publisher = {ACM Press},
  28  address = {New York, NY, USA},
  29 }
  30
  31 @inproceedings { fw:transdich,
  32    author = "M. Fredman and D. E. Willard",
  33    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
  34    booktitle = "{Proceedings of FOCS'90}",
  35    pages = "719--725",
  36    year = "1990"
  37 }
  38
  39 @article{ boas:vebt,
  40   author    = {Peter van Emde Boas},
  41   title     = {Preserving Order in a Forest in Less Than Logarithmic Time
  42                and Linear Space.},
  43   journal   = {Inf. Process. Lett.},
  44   volume    = {6},
  45   number    = {3},
  46   year      = {1977},
  47   pages     = {80-82},
  48   bibsource = {DBLP, http://dblp.uni-trier.de}
  49 }
  50
  51 @article{ benamram:pm,
  52     author = "Ben-Amram, Amir M.",
  53     title = "What is a ``Pointer Machine''?",
  54     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
  55     volume = "26",
  56     year = "1995",
  57     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
  58
  59 @article{ matsui:planar,
  60     author = "Tomomi Matsui",
  61     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
  62     journal = "Discrete Applied Mathematics",
  63     volume = "58",
  64     year = "1995",
  65     pages = "91--94",
  66     url = "citeseer.nj.nec.com/2319.html"
  67 }
  68
  69 @article{ chazelle:ackermann,
  70     author = "Bernard Chazelle",
  71     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
  72     journal = jacm,
  73     volume = "47",
  74     pages = "1028--1047",
  75     year = "2000"
  76 }
  77
  78 @article{ nesetril:history,
  79     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
  80     title = "{Some remarks on the history of MST-problem}",
  81     journal = "Archivum Mathematicum",
  82     volume = "33",
  83     pages = "15--22",
  84     year = "1997"
  85 }
  86
  87 @article{ nesetril:boruvka,
  88     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
  89     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
  90     journal = "Discrete Mathematics",
  91     volume = "233(1--3)",
  92     pages = "3--36",
  93     year = "2001"
  94 }
  95
  96 @incollection { nesetril:minors,
  97     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
  98     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
  99     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
 100     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
 101     year = "2003",
 102     pages = "651--664",
 103     publisher = "Springer Verlag"
 104 }
 105
 106 @article { boruvka:ojistem,
 107     author = "Otakar Bor{\accent23u}vka",
 108     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 109     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 110     volume = "III",
 111     year = "1926",
 112     pages = "37--58",
 113     note = "Czech with German summary"
 114 }
 115
 116 @article { boruvka:networks,
 117     author = "Otakar Bor{\accent23u}vka",
 118     title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'y{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}",
 119     journal = "Elektronick\'y obzor",
 120     volume = "15",
 121     year = "1926",
 122     pages = "153--154",
 123     note = "Czech"
 124 }
 125
 126 @article { jarnik:ojistem,
 127     author = "Vojt\v{e}ch Jarn\'\i{}k",
 128     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 129     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 130     volume = "VI",
 131     year = "1930",
 132     pages = "57--63",
 133     note = "Czech"
 134 }
 135
 136 @book { tarjan:dsna,
 137     author = "Robert E. Tarjan",
 138     title = "{Data structures and network algorithms}",
 139     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
 140     volume = 44,
 141     year = "1983",
 142     publisher = "SIAM"
 143 }
 144
 145 @article { gh:history,
 146     author = "R. L. Graham and P. Hell",
 147     title = "{On the history of the minimum spanning tree problem}",
 148     journal = "{Annals of the History of Computing}",
 149     volume = "7",
 150     year = "1985",
 151     pages = "43--57"
 152 }
 153
 154 @techreport { pettie:ackermann,
 155     author = "Seth Pettie",
 156     title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
 157     institution = "Univ. of Texas at Austin",
 158     year = "1999",
 159     number = "TR99-23",
 160     type = "Tech Report"
 161 }
 162
 163 @inproceedings { pettie:optimal,
 164    author = "Seth Pettie and Vijaya Ramachandran",
 165    title = "{An Optimal Minimum Spanning Tree Algorithm}",
 166    booktitle = "{Proceedings of ICALP'2000}",
 167    year = "2000",
 168    publisher = "Springer Verlag",
 169    pages = "49--60"
 170 }
 171
 172 @article { pettie:alpha,
 173   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
 174   author={Pettie, S.},
 175   year={1999},
 176   publisher={University of Texas at Austin Austin, TX, USA}
 177 }
 178
 179 @article { karger:randomized,
 180    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 181    title = "{Linear expected-time algorithms for connectivity problems}",
 182    journal = jacm,
 183    volume = "42",
 184    pages = "321--328",
 185    year = "1995"
 186 }
 187
 188 @article { frederickson:online,
 189    author = "Greg N. Frederickson",
 190    title = "{Data structures for on-line updating of minimum spanning trees}",
 191    journal = "{SIAM Journal on Computing}",
 192    volume = "14",
 193    pages = "781--798",
 194    year = "1985"
 195 }
 196
 197 @article { mm:mst,
 198    author = "Martin Mare\v{s}",
 199    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 200    journal = "{Archivum Mathematicum}",
 201    volume = "40",
 202    pages = "315--320",
 203    year = "2004"
 204 }
 205
 206 @article{ ft:fibonacci,
 207  author = {Michael L. Fredman and Robert Endre Tarjan},
 208  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 209  journal = {J. ACM},
 210  volume = {34},
 211  number = {3},
 212  year = {1987},
 213  issn = {0004-5411},
 214  pages = {596--615},
 215  doi = {http://doi.acm.org/10.1145/28869.28874},
 216  publisher = {ACM Press},
 217  address = {New York, NY, USA},
 218  }
 219
 220 @article{ komlos:verify,
 221   author    = {J{\'a}nos Koml{\'o}s},
 222   title     = {Linear verification for spanning trees.},
 223   journal   = {Combinatorica},
 224   volume    = {5},
 225   number    = {1},
 226   year      = {1985},
 227   pages     = {57--65},
 228   bibsource = {DBLP, http://dblp.uni-trier.de}
 229 }
 230
 231 @inproceedings{ king:verify,
 232     author = "Valerie King",
 233     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
 234     booktitle = "Workshop on Algorithms and Data Structures",
 235     pages = "440--448",
 236     year = "1995",
 237     url = "citeseer.ist.psu.edu/king95simpler.html" }
 238
 239 @article{ king:verifytwo,
 240   title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
 241   author={King, Valerie},
 242   journal={Algorithmica},
 243   volume={18},
 244   pages={263--270},
 245   year={1997}
 246 }
 247
 248 @book { schrijver,
 249     author = "Alexander Schrijver",
 250     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
 251     series = "Algorithms and Combinatorics",
 252     volume = 24,
 253     year = 2003,
 254     publisher = "Springer Verlag"
 255 }
 256
 257 @inproceedings{ thorup:aczero,
 258  author = {Mikkel Thorup},
 259  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 260  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
 261  year = {2003},
 262  isbn = {0-89871-538-5},
 263  pages = {699--707},
 264  location = {Baltimore, Maryland},
 265  publisher = {Society for Industrial and Applied Mathematics},
 266  address = {Philadelphia, PA, USA},
 267 }
 268
 269 @article{ kruskal:mst,
 270   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
 271   author={Kruskal Jr, J.B.},
 272   journal={Proceedings of the American Mathematical Society},
 273   volume={7},
 274   number={1},
 275   pages={48--50},
 276   year={1956},
 277   publisher={JSTOR}
 278 }
 279
 280 @book{ diestel:gt,
 281   title={{Graph Theory}},
 282   author={Diestel, R.},
 283   year={2005},
 284   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
 285 }
 286
 287 @article{ thorup:pq,
 288   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 289   author={Thorup, M.},
 290   journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
 291   pages={149--158},
 292   year={2003},
 293   publisher={ACM Press New York, NY, USA}
 294 }
 295
 296 @article{ graham:msthistory,
 297   title={{On the history of the minimum spanning tree problem}},
 298   author={Graham, R.L. and Hell, P.},
 299   journal={Annals of the History of Computing},
 300   volume={7},
 301   number={1},
 302   pages={43--57},
 303   year={1985}
 304 }
 305
 306 @article{ cayley:trees,
 307   title={{A theorem on trees}},
 308   author={Cayley, Arthur},
 309   journal={Quart. J. Math},
 310   volume={23},
 311   year={1889},
 312   pages={376--378}
 313 }
 314
 315 @article{ dijkstra:mst,
 316   title={{A note on two problems in connexion with graphs}},
 317   author = "Dijkstra, E. W.",
 318   journal={Numerische Mathematik},
 319   volume={1},
 320   number={1},
 321   pages={269--271},
 322   year={1959},
 323   publisher={Springer}
 324 }
 325
 326 @article{ prim:mst,
 327   author = "Prim, R. C.",
 328   title = "Shortest connection networks and some generalizations",
 329   journal = "Bell System Technical Journal",
 330   volume = "36",
 331   year = "1957",
 332   pages={567--574},
 333 }
 334
 335 @article{ choquet:mst,
 336   title={{Etude de certains r{\'e}seaux de routes}},
 337   author={Choquet, Gustave},
 338   journal={Comptes-rendus de l'Académie des Sciences},
 339   volume={206},
 340   pages={310},
 341   year={1938},
 342   note={French}
 343 }
 344
 345 @incollection { sollin:mst,
 346   title={{Le trace de canalisation}},
 347   author={Sollin, M.},
 348   booktitle={Programming, Games, and Transportation Networks},
 349   editor={Berge, C. and Ghouilla-Houri, A.},
 350   publisher={Wiley, New York},
 351   year={1965},
 352   note={French}
 353 }
 354
 355 @article{ boyer:cutting,
 356   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
 357   author={Boyer, J.M. and Myrvold, W.J.},
 358   journal={Journal of Graph Algorithms and Applications},
 359   volume={8},
 360   number={3},
 361   pages={241--273},
 362   year={2004}
 363 }
 364
 365 @inproceedings{ takaoka:twothree,
 366   title={{Theory of 2-3 Heaps}},
 367   author={Takaoka, T. and Christchurch, N. Z.},
 368   booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
 369   location={Tokyo, Japan},
 370   year={1999},
 371   pages={41--50},
 372   publisher={Springer},
 373   series={{Lecture Notes in Computer Science}},
 374   volume={1627}
 375 }
 376
 377 @inproceedings{ takaoka:trinomial,
 378   title={{Theory of Trinomial Heaps}},
 379   author={Takaoka, Tadao},
 380   booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
 381   location={Sydney, Australia},
 382   year={2000},
 383   pages={362--372},
 384   publisher={Springer},
 385   series={{Lecture Notes in Computer Science}},
 386   volume={1858}
 387 }
 388
 389 @book{ clrs,
 390   title={{Introduction to Algorithms}},
 391   author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
 392   year={2001},
 393   publisher={McGraw-Hill}
 394 }
 395
 396 @inproceedings{ pettie:onlineverify,
 397   author = "S. Pettie",
 398   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
 399     tree verification problem",
 400   booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
 401   year = "2002",
 402   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
 403 }
 404
 405 @article{ dixon:verify,
 406     author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
 407     title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
 408     journal = "SIAM J. Comput.",
 409     volume = "21",
 410     number = "6",
 411     pages = "1184-1192",
 412     year = "1992",
 413     url = "citeseer.ist.psu.edu/dixon92verification.html"
 414 }
 415
 416 inproceedings{ pettie:minirand,
 417  author = {Seth Pettie and Vijaya Ramachandran},
 418  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
 419  booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
 420  year = {2002},
 421  isbn = {0-89871-513-X},
 422  pages = {713--722},
 423  location = {San Francisco, California},
 424  publisher = {Society for Industrial and Applied Mathematics},
 425  address = {Philadelphia, PA, USA}
 426 }
 427
 428 @article{ buchsbaum:verify,
 429   title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
 430   author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
 431   journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
 432   pages={279--288},
 433   year={1998},
 434   publisher={ACM Press New York, NY, USA}
 435 }
 436
 437 @article{ bacala:parametric,
 438   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
 439   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
 440   journal={Theoretical Computer Science},
 441   volume={181},
 442   number={1},
 443   pages={57--74},
 444   year={1997},
 445   publisher={Elsevier}
 446 }
 447
 448 @inproceedings{ katriel:cycle,
 449   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
 450   title = "A practical minimum spanning tree algorithm using the cycle property",
 451   booktitle = "11th European Symposium on Algorithms(ESA)",
 452   number = "2832",
 453   series = "LNCS",
 454   pages = "679--690",
 455   publisher = "Springer",
 456   year = "2003",
 457   url = "citeseer.ist.psu.edu/katriel03practical.html"
 458 }
 459
 460 @article{ alstrup:nca,
 461   title={{Nearest common ancestors: a survey and a new distributed algorithm}},
 462   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
 463   journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
 464   pages={258--264},
 465   year={2002},
 466   publisher={ACM Press New York, NY, USA}
 467 }
 468
 469 @article{ gabow:mst,
 470   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
 471   author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
 472   journal={Combinatorica},
 473   volume={6},
 474   number={2},
 475   pages={109--122},
 476   year={1986},
 477   publisher={Springer}
 478 }
 479
 480 @Unpublished{ eisner:tutorial,
 481   author =       {Jason Eisner},
 482   title =        {State-of-the-Art Algorithms for Minimum Spanning
 483                   Trees: A Tutorial Discussion},
 484   note =         {Manuscript available online (78 pages), University of Pennsylvania},
 485   year =         1997,
 486   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
 487 }
 488
 489 @article{ aho:lca,
 490   title={{On finding lowest common ancestors in trees.}},
 491   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
 492   journal={SIAM Journal on Computing},
 493   volume={5},
 494   pages={115--132},
 495   year={1976}
 496 }
 497
 498 @book{ knuth:fundalg,
 499  author = {Donald E. Knuth},
 500  title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
 501  year = {1997},
 502  isbn = {0-201-89683-4},
 503  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 504  address = {Redwood City, CA, USA},
 505 }
 506
 507 @book{ knuth:seminalg,
 508  author = {Donald E. Knuth},
 509  title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
 510  year = {1997},
 511  isbn = {978-0-201-89684-8},
 512  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 513  address = {Redwood City, CA, USA},
 514 }
 515
 516 @inproceedings{ hagerup:wordram,
 517  author = {Torben Hagerup},
 518  title = {{Sorting and Searching on the Word RAM}},
 519  booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
 520  year = {1998},
 521  isbn = {3-540-64230-7},
 522  pages = {366--398},
 523  publisher = {Springer-Verlag},
 524  address = {London, UK},
 525 }
 526
 527 @inproceedings{ cook:ram,
 528  author = {Stephen A. Cook and Robert A. Reckhow},
 529  title = {Time-bounded random access machines},
 530  booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
 531  year = {1972},
 532  pages = {73--80},
 533  location = {Denver, Colorado, United States},
 534  doi = {http://doi.acm.org/10.1145/800152.804898},
 535  publisher = {ACM},
 536  address = {New York, NY, USA},
 537 }
 538
 539 @book{ okasaki:funcds,
 540   author = {Chris Okasaki},
 541   title = {Purely Functional Data Structures},
 542   year = {1999},
 543   publisher = {Cambridge University Press}
 544 }
 545
 546 @book { intel:pentium,
 547   author = {{Intel Corp.}},
 548   title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
 549   year = {2007},
 550   publisher = {Intel Corp.},
 551   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
 552 }
 553
 554 @article{ hagerup:dd,
 555   title={{Deterministic Dictionaries}},
 556   author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
 557   journal={J. Algorithms},
 558   volume={41},
 559   number={1},
 560   pages={69--85},
 561   year={2001}
 562 }
 563
 564 @article{ fredman:sst,
 565   title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
 566   author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
 567   journal={Journal of the ACM (JACM)},
 568   volume={31},
 569   number={3},
 570   pages={538--544},
 571   year={1984},
 572   publisher={ACM Press New York, NY, USA}
 573 }
 574
 575 @book{ motwani:randalg,
 576   title={{Randomized Algorithms}},
 577   author={Motwani, R. and Raghavan, P.},
 578   year={1995},
 579   publisher={Cambridge University Press}
 580 }
 581
 582 @article{ fw:fusion,
 583   title={{Surpassing the information theoretic bound with fusion trees}},
 584   author={Fredman, M.L. and Willard, D.E.},
 585   journal={Journal of Computer and System Sciences},
 586   volume={47},
 587   number={3},
 588   pages={424--436},
 589   year={1993},
 590   publisher={Academic Press, Inc. Orlando, FL, USA}
 591 }
 592
 593 @article{ han:detsort,
 594   title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
 595   author={Han, Y.},
 596   journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
 597   pages={602--608},
 598   year={2002},
 599   publisher={ACM Press New York, NY, USA}
 600 }
 601
 602 @article{ hanthor:randsort,
 603   title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
 604   author={Han, Y. and Thorup, M.},
 605   journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
 606   pages={135--144},
 607   year={2002},
 608   publisher={IEEE Computer Society Washington, DC, USA}
 609 }
 610
 611 @article{ ito:newrap,
 612   title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
 613   author={Ito, M. and Takagi, N. and Yajima, S.},
 614   journal={Proc. 12th IEEE Symp. Computer Arithmetic},
 615   pages={2--9},
 616   year={1995}
 617 }
 618
 619 @article{ brodnik:lsb,
 620   title={{Computation of the least significant set bit}},
 621   author={Brodnik, A.},
 622   journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
 623   year={1993}
 624 }