Encyclopedia of algorithms / ed. by Kao M.-Y. - New York: Springer, 2008. - liii, 1166 p.: ill. - (Springer reference). - Bibloigr.: p.1053-1155. - Ind.: p.1157-1166. - ISBN 978-0-387-30770-1  Место хранения:   020 | Институт вычислительного моделирования СО РАН | Красноярск | Библиотека

Оглавление / Contents

Abelian Hidden Subgroup Problem ................................. 1 1995; Kitaev Adaptive Partitions ............................................. 4 1986; Du, Pan, Shing Adwords Pricing ................................................. 7 2007; Bu, Deng, Qi Algorithm DC-Tree for к Servers on Trees ........................ 9 1991; Chrobak, Larmore Algorithmic Cooling ............................................ 11 1999; Schulman, Vazirani 2002; Boykin, Моr, Roychowdhury, Vatan, Vrijen Algorithmic Mechanism Design ................................... 16 1999; Nisan, Ronen Algorithms for Spanners in Weighted Graphs ..................... 25 2003; Baswana, Sen All Pairs Shortest Paths in Sparse Graphs ...................... 28 2004; Pettie All Pairs Shortest Paths via Matrix Multiplication ............. 31 2002; Zwick Alternative Performance Measures in Online Algorithms .......... 34 2000; Koutsoupias, Papadimitriou Analyzing Cache Misses ......................................... 37 2003; Mehlhorn, Sanders Applications of Geometric Spanner Networks ..................... 40 2002; Gudmundsson, Levcopoulos, Narasimhan, Smid Approximate Dictionaries ....................................... 43 2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh Approximate Regular Expression Matching ........................ 46 1995; Wu, Manber, Myers Approximate Tandem Repeats ..................................... 48 2001; Landau, Schmidt, Sokol 2003; Kolpakov, Kucherov Approximating Metric Spaces by Tree Metrics .................... 51 1996; Bartal, Fakcharoenphol, Rao, Talwar 2004; Bartal, Fakcharoenphol, Rao, Talwar Approximations of Bimatrix Nash Equilibria ..................... 53 2003; Lipton, Markakis, Mehta 2006; Daskalaskis, Mehta, Papadimitriou 2006; Kontogiannis, Panagopoulou, Spirakis Approximation Schemes for Bin Packing .......................... 57 1982; Karmarker, Karp Approximation Schemes for Planar Graph Problems ................ 59 1983; Baker 1994; Baker Arbitrage in Frictional Foreign Exchange Market ................ 62 2003; Cai, Deng Arithmetic Coding for Data Compression ......................... 65 1994; Howard, Vitter Assignment Problem ............................................. 68 1955; Kuhn 1957; Munkres Asynchronous Consensus Impossibility ........................... 70 1985; Fischer, Lynch, Paterson Atomic Broadcast ............................................... 73 1995; Cristian, Aghili, Strong, Dolev Attribute-Efficient Learning ................................... 77 1987; Littlestone Automated Search Tree Generation ............................... 78 2004; Gramm, Guo, Hüffner, Niedermeier Backtracking Based/c-SAT Algorithms ............................ 83 2005; Paturi, Pudldk, Saks, Zane Best Response Algorithms for Selfish Routing ................... 86 2005; Fotakis, Kontogiannis, Spirakis Bidimensionality ............................................... 88 2004; Demaine, Fomin, Hajiaghayi, Thilikos Binary Decision Graph .......................................... 90 1986; Bryant Bin Packing .................................................... 94 1997; Coffman, Garay, Johnson Boosting Textual Compression ................................... 97 2005; Ferragina, Giancarlo, Manzini, Sciortino Branchwidth of Graphs ......................................... 101 2003; Fomin, Thilikos Broadcasting in Geometric Radio Networks ...................... 105 2001; Dessmark, Pelc B-trees ....................................................... 108 1972; Bayer, McCreight Burrows-Wheeler Transform ..................................... 112 1994; Burrows, Wheeler Byzantine Agreement ........................................... 116 1980; Pease, Shostak, Lamport Cache-Oblivious B-Tree ........................................ 121 2005; Bender, Demaine, Farach-Colton Cache-Oblivious Model ......................................... 123 1999; Frigo, Leiserson, Prokop, Ramachandran Cache-Oblivious Sorting ....................................... 126 1999; Frigo, Leiserson, Prokop, Ramachandran Causal Order, Logical Clocks, State Machine Replication ....... 129 1978; Lamport Certificate Complexity and Exact Learning ..................... 131 1995; Hellerstein, Pilliapakkamnatt, Raghavan, Wilkins Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks ................................................. 134 2005; Alicherry, Bhatia, Li Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach ...................................................... 138 1994; Yang, Wong Circuit Placement ............................................. 143 2000; Caldwell, Kahng, Markov 2002; Kennings, Markov 2006; Kennings, Vorwerk Circuit Retiming .............................................. 146 1991; Leiserson, Saxe Circuit Retiming: An Incremental Approach ..................... 149 2005; Zhou Clock Synchronization ......................................... 152 1994; Patt-Shamir, Rajsbaum Closest String and Substring Problems ......................... 155 2002; Li, Ma, Wang Closest Substring ............................................. 156 2005; Marx Color Coding .................................................. 158 1995; Alon, Yuster, Zwick Communication in Ad Hoc Mobile Networks Using Random Walks .... 161 2003; Chatzigiannakis, Nikoletseas, Spirakis Competitive Auction ........................................... 165 2001; Goldberg, Hartline, Wright 2002; Fiat, Goldberg, Hartline, Karlin Complexity of Bimatrix Nash Equilibria ........................ 166 2006; Chen, Deng Complexity of Core ............................................ 168 2001; Fang, Zhu, Cai, Deng Compressed Pattern Matching ................................... 171 2003; Kida, Matsumoto, Shibata, Takeda, Shinohara, Arikawa Compressed Suffix Array ....................................... 174 2003; Grossi, Gupta, Vitter Compressed Text Indexing ...................................... 176 2005; Ferragina, Manzini Compressing Integer Sequences and Sets ........................ 178 2000; Moffat, Stuiver Computing Pure Equilibria in the Game of Parallel Links ....... 183 2002; Fotakis, Kontogiannis, Koutsoupias, Mavronicolas, Spirakis 2003; Even-Dar, Kesselman, Mansour 2003; Feldman, Gairing, Lucking, Monien, Rode Concurrent Programming, Mutual Exclusion ...................... 188 1965; Dijkstra Connected Dominating Set ...................................... 191 2003; Cheng, Huang, Li, Wu, Du Connectivity and Fault-Tolerance in Random Regular Graphs ..... 195 2000; Nikoletseas, Palem, Spirakis, Yung Consensus with Partial Synchrony .............................. 198 1988; Dwork, Lynch, Stockmeyer Constructing a Galled Phylogenetic Network .................... 202 2006; Jansson, Nguyen, Sung CPU Time Pricing .............................................. 205 2005; Deng, Huang, Li Critical Range for Wireless Networks .......................... 207 2004; Wan, Yi Cryptographic Hardness of Learning ............................ 210 1994; Kearns, Valiant Cuckoo Hashing ................................................ 212 2001; Pagh, Rodler Data Migration ................................................ 217 2004; Khuller, Kim, Wan Data Reduction for Domination in Graphs ....................... 220 2004; Alber, Fellows, Niedermeier Decoding Reed-Solomon Codes ................................... 222 1999; Guruswami, Sudan Decremental All-Pairs Shortest Paths .......................... 226 2004; Demetrescu, Italiano Degree-Bounded Planar Spanner with Low Weight ................. 228 2005; Song, Li, Wang Degree-Bounded Trees .......................................... 231 1994; Ftirer, Raghavachari Deterministic Broadcasting in Radio Networks .................. 233 2000; Chrobak, Gqsieniec, Rytter Deterministic Searching on the Line ........................... 235 1988; Baeza-Yates, Culberson, Rawlins Dictionary-Based Data Compression ............................. 236 1977; Ziv, Lempel Dictionary Matching and Indexing (Exact and with Errors) ...... 240 2004; Cole, Gottlieb, Lewenstein Dilation of Geometric Networks ................................ 244 2005; Ebbers-Ваитапп, Grune, Karpinski, Klein, Kutz, Knauer, Lingas Directed Perfect Phylogeny (Binary Characters) ................ 246 1991; Gusfield Direct Routing Algorithms ..................................... 248 2006; Busch, Magdon-Ismail, Mavronicolas, Spirakis Distance-Based Phylogeny Reconstruction (Fast-Converging) ..... 251 2003; King, Zhang, Zhou Distance-Based Phylogeny Reconstruction (Optimal Radius) ...... 253 1999; Atteson 2005; Elias, Lagergren Distributed Algorithms for Minimum Spanning Trees ............. 256 1983; Gallager, Humblet, Spira Distributed Vertex Coloring ................................... 258 2004; Finocchi, Panconesi, Silvestri Dynamic Trees ................................................. 260 2005; Tarjan, Werneck Edit Distance Under Block Operations .......................... 265 2000; Cormode, Paterson, Sahinalp, Vishkin 2000; Muthukrishnan, Sahinalp Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds ....................................... 267 1993; Gusfield Engineering Algorithms for Computational Biology .............. 270 2002; Bader, Moret, Warnow Engineering Algorithms for Large Network Applications ......... 272 2002; Schulz, Wagner, Zaroliagis Engineering Geometric Algorithms .............................. 274 2004; Halperin Equivalence Between Priority Queues and Sorting ............... 278 2002; Thorup Euclidean Traveling Salesperson Problem ....................... 281 1998; Arora Exact Algorithms for Dominating Set ........................... 284 2005; Fomin, Grandoni, Kratsch Exact Algorithms for General CNF SAT .......................... 286 1998; Hirsch 2003; Schuler Exact Graph Coloring Using Inclusion-Exclusion ................ 289 2006; Bjorklund, Husfeldt Experimental Methods for Algorithm Analysis ................... 290 2001; McGeoch External Sorting and Permuting ................................ 291 1988; Aggarwal, Vitter Facility Location ............................................. 299 1997; Shmoys, Tardos, Aardal Failure Detectors ............................................. 304 1996; Chandra, Toueg False-Name-Proof Auction ...................................... 308 2004; Yokoo, Sakurai, Matsubara Fast Minimal Triangulation .................................... 310 2005; Heggernes, Telle, Villanger Fault-Tolerant Quantum Computation ............................ 313 1996; Shor, Aharonov, Ben-Or, Kitaev Floorplan and Placement ....................................... 317 1994; Kajitani, Nakatake, Murata, Fujiyoshi Flow Time Minimization ........................................ 320 2001; Becchetti, Leonardi, Marchetti-Spaccamela, Pruhs FPGA Technology Mapping ....................................... 322 1992; Cong, Ding Fractional Packing and Covering Problems ...................... 326 1991; Plotkin, Shmoys, Tardos 1995; Plotkin, Shmoys, Tardos Fully Dynamic All Pairs Shortest Paths ........................ 329 2004; Demetrescu, Italiano Fully Dynamic Connectivity .................................... 331 2001; Holm, de Lichtenberg, Thorup Fully Dynamic Connectivity: Upper and Lower Bounds ............ 332 2000; Thorup Fully Dynamic Higher Connectivity ............................. 335 1997; Eppstein, Galil, Italiano, Nissenzweig Fully Dynamic Higher Connectivity for Planar Graphs ........... 337 1998; Eppstein, Galil, Italiano, Spencer Fully Dynamic Minimum Spanning Trees .......................... 339 2000; Holm, de Lichtenberg, Thorup Fully Dynamic Planarity Testing ............................... 342 1999; Galil, Italiano, Sarnak Fully Dynamic Transitive Closure .............................. 343 1999; King Gate Sizing ................................................... 345 2002; Sundararajan, Sapatnekar, Parhi General Equilibrium ........................................... 347 2002; Deng, Papadimitriou, Safra Generalized Steiner Network ................................... 349 2001; Jain Generalized Two-Server Problem ................................ 351 2006; Sitters, Stougie Generalized Vickrey Auction ................................... 353 1995; Varian Geographic Routing ............................................ 355 2003; Kuhn, Wattenhofer, Zollinger Geometric Dilation of Geometric Networks ...................... 358 2006; Dumitrescu, Ebbers-Baumann, Grune, Klein, Knauer, Rote Geometric Spanners ............................................ 360 2002; Gudmundsson, Levcopoulos, Narasimhan Gomory-Hu Trees ............................................... 364 2007; Bhalgat Hariharan, Kavitha, Panigrahi Graph Bandwidth ............................................... 366 1998; Feige 2000; Feige Graph Coloring ................................................ 368 1994; Karger Motwani, Sudan 1998; Karger Motwani, Sudan Graph Connectivity ...................................... 371 1994; Khuller, Vishkin Graph Isomorphism ............................................. 373 1980; McKay Greedy Approximation Algorithms ............................... 376 2004; Ruan Du, Jia, Wu, Li, Ко Greedy Set-Cover Algorithms ................................... 379 1974-1979, Chvatal, Johnson, Lovdsz, Stein Hamilton Cycles in Random Intersection Graphs ................. 383 2005; Efthymiou, Spirakis Hardness of Proper Learning ................................... 385 1988; Pitt, Valiant High Performance Algorithm Engineering for Large-scale Problems ...................................................... 387 2005; Bader Hospitals/Residents Problem ................................... 390 1962; Gale, Shapley Implementation Challenge for Shortest Paths ................... 395 2006; Demetrescu Goldberg Johnson Implementation Challenge for TSP Heuristics ................... 398 2002; Johnson, McGeoch Implementing Shared Registers in Asynchronous Message- Passing Systems ............................................... 400 1995; Attiya, Bar-Noy, Dolev Incentive Compatible Selection ................................ 403 2006; Chen Deng Liu Independent Sets in Random Intersection Graphs ................ 405 2004; Nikoletseas, Raptopoulos, Spirakis Indexed Approximate String Matching ........................... 408 2006; Chan, Lam, Sung, Tarn, Wong Inductive Inference ........................................... 411 1983; Case Smith l/0-model ..................................................... 413 1988; Aggarwal, Vitter Kinetic Data Structures ....................................... 417 1999; Basch, Guibas, Hershberger Knapsack ...................................................... 419 1975; Ibarra, Kim Learning with the Aid of an Oracle ............................ 423 1996; Bshouty, Cleve, Gavalda, Kannan, Tamon Learning Automata ............................................. 425 2000; Beimel, Bergadano, Bshouty, Kushilevitz, Varricchio Learning Constant-Depth Circuits .............................. 429 1993; Linial, Mansour, Nisan Learning DNF Formulas ......................................... 431 1997; Jackson Learning Heavy Fourier Coefficients of Boolean Functions ...... 434 1989; Goldreich Levin Learning with Malicious Noise ................................. 436 1993; Kearns Li Learning Significant Fourier Coefficients over Finite Abelian Groups ................................................ 438 2003; Akavia, Goldwasser, Safra LEDA: a Library of Efficient Algorithms ....................... 442 1995; Mehlhorn, Naher Leontief Economy Equilibrium .................................. 444 2005; Codenotti, Saberi, Varadarajan, Ye 2005; Ye Linearity Testing/Testing Hadamard Codes ...................... 446 1990; Blum, Luby, Rubinfeld Linearizability ............................................... 450 1990; Herlihy, Wing List Decoding near Capacity: Folded RS Codes .................. 453 2006; Guruswami, Rudra List Scheduling ............................................... 455 1966; Graham Load Balancing ................................................ 457 1994; Azar, Broder, Karlin 1997; Azar Kalyanasundaram, Plotkin Pruhs Waarts Local Alignment (with Affine Gap Weights) ..................... 459 1986; Altschul, Erickson Local Alignment (with Concave Gap Weights) .................... 461 1988; Miller, Myers Local Approximation of Covering and Packing Problems .......... 463 2003-2006; Kuhn, Moscibroda, Nieberg, Wattenhofer Local Computation in Unstructured Radio Networks .............. 466 2005; Moscibroda, Wattenhofer Local Search Algorithms for /cSAT ............................. 468 1999; Schoning Local Search for/f-medians and Facility Location .............. 470 2001; Arya, Garg, Khandekar, Meyerson, Munagala, Pandit Lower Bounds for Dynamic Connectivity ......................... 473 2004; Patrascu, Demaine Low Stretch Spanning Trees .................................... 477 2005; Elkin, Emek, Spielman, Teng LP Decoding ................................................... 478 2002 and later; Feldman, Karger, Wainwright Majority Equilibrium .......................................... 483 2003; Chen, Deng, Fang, Tian Market Games and Content Distribution ......................... 485 2005; Mirrokni Max Cut ....................................................... 489 1994; Goemans, Williamson 1995; Goemans, Williamson Maximum Agreement Subtree (of 2 Binary Trees) ................. 492 1996; Cole, Hariharan Maximum Agreement Subtree (of 3 or More Trees) ................ 495 1995; Farach, Przytycka, Thorup Maximum Agreement Supertree ................................... 497 2005; Jansson, Ng, Sadakane, Sung Maximum Compatible Tree ....................................... 499 2001; Ganapathy, Warnow Maximum-Density Segment ....................................... 502 1994; Huang Maximum Matching .............................................. 504 2004; Mucha, Sankowski Maximum-scoring Segment with Length Restrictions .............. 506 2002; Lin, Jiang, Chao Maximum Two-Satisfiability .................................... 507 2004; Williams Max Leaf Spanning Tree ........................................ 511 2005; Estivill-Castro, Fellows, Langston, Rosamond Metrical Task Systems ......................................... 514 1992; Borodin, Linial, Saks Metric TSP .................................................... 517 1976; Christofides Minimum Bisection ............................................. 519 1999; Feige, Krauthgamer Minimum Congestion Redundant Assignments ...................... 522 2002; Fotakis, Spirakis Minimum Energy Broadcasting in Wireless Geometric Networks .... 526 2005; Ambühl Minimum Energy Cost Broadcasting in Wireless Networks ......... 528 2001; Wan, Calinescu, Li, Frieder Minimum Flow Time ............................................. 531 1997; Leonardi, Raz Minimum Geometric Spanning Trees .............................. 533 1999; Krznaric, Levcopoulos, Nilsson Minimum /(-Connected Geometric Networks ....................... 536 2000; Czumaj, Lingas Minimum Makespan on Unrelated Machines ........................ 539 1990; Lenstra, Shmoys, Tardos Minimum Spanning Trees ........................................ 541 2002; Pettie, Ramachandran Minimum Weighted Completion Time .............................. 544 1999; Afrati et al. Minimum Weight Triangulation .................................. 546 1998; Levcopoulos, Krznaric Mobile Agents and Exploration ................................. 548 1952; Shannon Multicommodity Flow, Well-linked Terminals and Routing Problems ...................................................... 551 2005; Chekuri, Khanna, Shepherd Multicut ...................................................... 554 1993; Garg, Vazirani, Yannakakis 1996; Garg, Vazirani, Yannakakis Multidimensional Compressed Pattern Matching .................. 556 2003; Amir, Landau, Sokol Multidimensional String Matching .............................. 559 1999; Kärkkäinen, Ukkonen Multi-level Feedback Queues ................................... 562 1968; Coffman, Kleinrock Multiple Unit Auctions with Budget Constraint ................. 563 2005; Borgs, Chayes, Immorlica, Mahdian, Saberi 2006; Abrams Multiplex PCR for Gap Closing (Whole-genome Assembly) ......... 565 2002; Alon, Beigel, Kasif, Rudich, Sudakov MultiwayCut ................................................... 567 1998; Calinescu, Karloff, Rabani Nash Equilibria and Dominant Strategies in Routing ............ 571 2005; Wang, Li, Chu Nearest Neighbor Interchange and Related Distances ............ 573 1999; DasGupta, He, Jiang, Li, Tromp, Zhang Negative Cycles in Weighted Digraphs .......................... 576 1994; Kavvadias, Pantziou, Spirakis, Zaroliagis Non-approximabilityof BimatrixNash Equilibria ................. 578 2006; Chen, Deng, Teng Non-shared Edges .............................................. 579 1985; Day Nucleolus ..................................................... 581 2006; Deng, Fang, Sun Oblivious Routing ............................................. 585 2002; Racke Obstacle Avoidance Algorithms in Wireless Sensor Networks ..... 588 2007; Powell, Nikoletseas 0(log log n)-competitive Binary Search Tree ................... 592 2004; Demaine, Harmon, Iacono, Patrascu Online Interval Coloring ...................................... 594 1981; Kierstead, Trotter Online List Update ............................................ 598 1985; Sleator, Tarjan Online Paging and Caching ..................................... 601 1985-2002; multiple authors Optimal Probabilistic Synchronous Byzantine Agreement ......... 604 1988; Feldman, Micali Optimal Stable Marriage ....................................... 606 1987; Irving, Leather, Gusfield P2P ........................................................... 611 2001; Stoica, Morris, Karger, Kaashoek, Balakrishnan Packet Routing ................................................ 616 1988; Leighton, Maggs, Rao Packet Switching in Multi-Queue Switches ...................... 618 2004; Azar, Richter; Albers, Schmidt Packet Switching in Single Buffer ............................. 621 2003; Bansal, Fleischer, Kimbrel, Mahdian, Schieber, Sviridenko РАС Learning .................................................. 622 1984; Valiant PageRank Algorithm ............................................ 624 1998; Brin, Page Paging ........................................................ 625 1985; Sleator, Tarjan, Fiat, Karp, Luby, McGeoch, Sleator, Young 1991; Sleator, Tarjan; Fiat, Karp, Luby, McGeoch, Sleator, Young Parallel Algorithms for Two Processors Precedence Constraint Scheduling ......................................... 627 2003; Jung, Serna, Spirakis Parallel Connectivity and Minimum Spanning Trees .............. 629 2001; Chong, Han, Lam Parameterized Algorithms for Drawing Graphs ................... 631 2004; Dujmovic, Whitesides Parameterized Matching ........................................ 635 1993; Baker Parameterized SAT ............................................. 639 2003; Szeider Peptide De Novo Sequencing with MS/MS ......................... 640 2005; Ma, Zhang, Liang Perceptron Algorithm .......................................... 642 1959; Rosenblatt Perfect Phylogeny (Bounded Number of States) .................. 644 1997; Kannan, Warnow Perfect Phylogeny Haplotyping ................................. 647 2005; Ding, Filkov, Gusfield Performance-Driven Clustering ................................. 650 1993; Rajaraman, Wong Phylogenetic Tree Construction from a Distance Matrix ......... 651 1989; Hein Planar Geometric Spanners ..................................... 653 2005; Bose, Smid, Gudmundsson Planarity Testing ............................................. 656 1976; Booth, Lueker Point Pattern Matching ........................................ 657 2003; Ukkonen, Lemstrom, Makinen Position Auction .............................................. 660 2005; Varian Predecessor Search ............................................ 661 2006; Patrascu, Thorup Price of Anarchy .............................................. 665 2005; Koutsoupias Price of Anarchy for Machines Models .......................... 667 2002; Czumaj, Vocking Probabilistic Data Forwarding in Wireless Sensor Networks ..... 671 2004; Chatzigiannakis, Dimitriou, Nikoletseas, Spirakis Quantization of Markov Chains ................................. 677 2004; Szegedy Quantum Algorithm for Checking Matrix Identities .............. 680 2006; Buhrman, Spalek Quantum Algorithm for the Collision Problem ................... 682 1998; Brassard, Hoyer, Tapp Quantum Algorithm for the Discrete Logarithm Problem .......... 683 1994; Shor Quantum Algorithm for Element Distinctness .................... 686 2004; Ambainis Quantum Algorithm for Factoring ............................... 689 1994; Shor Quantum Algorithm for Finding Triangles ....................... 690 2005; Magniez, Santha, Szegedy Quantum Algorithm for the Parity Problem ...................... 693 1985; Deutsch Quantum Algorithms for Class Group of a Number Field .......... 694 2005; Hallgren Quantum Algorithm for Search on Grids ......................... 696 2005; Ambainis, Kempe, Rivosh Quantum Algorithm for Solving the Pell's Equation ............. 698 2002; Hallgren Quantum Approximation of the Jones Polynomial ................. 700 2005; Aharonov, Jones, Landau Quantum Dense Coding .......................................... 703 1992; Bennett, Wiesner Quantum Error Correction ...................................... 705 1995; Shor Quantum Key Distribution ...................................... 708 1984; Bennett, Brassard 1991; Ebrt Quantum Search ................................................ 712 1996; Grover Quorums ....................................................... 715 1985; Garcia-Molina, Barbara Radiocoloringin Planar Graphs ............................. 721 2005; Fotakis, Nikoletseas, Papadopoulou, Spirakis Randomization in Distributed Computing ........................ 723 1996; Chandra Randomized Broadcasting in Radio Networks ..................... 725 1992; Reuven Bar-Yehuda, Oded Goldreich, Alon Itai Randomized Energy Balance Algorithms in Sensor Networks ....... 728 2005; Leone, Nikoletseas, Rolim Randomized Gossiping in Radio Networks ........................ 731 2001; Chrobak, Gacsieniec, Rytter Randomized Minimum Spanning Tree .............................. 732 1995; Karger, Klein, Tarjan Randomized Parallel Approximations to Max Flow ................ 734 1991; Serna, Spirakis Randomized Rounding ........................................... 737 1987; Raghavan, Thompson Randomized Searching on Rays or the Line ...................... 740 1993; Kao, Reif, Tate Random Planted 3-SAT .......................................... 742 2003; Flaxman Ranked Matching ............................................... 744 2005; Abraham, Irving, Kavitha, Mehlhorn Rank and Select Operations on Binary Strings .................. 748 1974;Elias Rate-Monotonic Scheduling ..................................... 751 1973; Liu, Layland Rectilinear Spanning Tree ..................................... 754 2002; Zhou, Shenoy, Nicholls Rectilinear Steiner Tree ...................................... 757 2004; Zhou Registers ..................................................... 761 1986; Lamport, Vitanyi, Awerbuch Regular Expression Indexing ................................... 764 2002; Chan, Garofalakis, Rastogi Regular Expression Matching ................................... 768 2004; Navarro, Raffinot Reinforcement Learning ........................................ 771 1992; Watkins Renaming ...................................................... 774 1990; Attiya, Bar-Noy, Dolev, Peleg, Reischuk RNA Secondary Structure Boltzmann Distribution ................ 777 2005; Miklos, Meyer, Nagy RNA Secondary Structure Prediction Including Pseudoknots ...... 780 2004; Lyngse RNA Secondary Structure Prediction by Minimum Free Energy ..... 782 2006; Ogurtsov, Shabalina, Kondrashov, Roytberg Robotics ...................................................... 785 1997; (Navigation) Blum, Raghavan, Schieber 1998; (Exploration) Deng, Kameda, Papadimitriou 2001; (Localization) Fleischer, Romanik, Schuierer, Trippen Robust Geometric Computation .................................. 788 2004; Li, Yap Routing ....................................................... 791 2003; Azar, Cohen, Fiat, Kaplan, Racke Routing in Geometric Networks ................................. 793 2003; Kuhn, Wattenhofer, Zhang, Zollinger Routing in Road Networks with Transit Nodes ................... 796 2007; Bast, Funke, Sanders, Schultes R-Trees ....................................................... 800 2004; Arge, de Berg, Haverkort, Yi Schedulers for Optimistic Rate Based Flow Control ............. 803 2005; Fatourou, Mavronicolas, Spirakis Scheduling with Equipartition ................................. 806 2000; Edmonds Selfish Unsplittable Flows: Algorithms for Pure Equilibria .... 810 2005; Fotakis, Kontogiannis, Spirakis Self-Stabilization ............................................ 812 1974; Dijkstra Separators in Graphs .......................................... 815 1998; Leighton, Rao 1999; Leighton, Rao Sequential Approximate String Matching ........................ 818 2003; Crochemore, Landau, Ziv-Ukelson 2004; Fredriksson, Navarro Sequential Circuit Technology Mapping ......................... 820 1998; Pan, Liu Sequential Exact String Matching .............................. 824 1994; Crochemore, Czumaj, Gatsieniec, Jarominek, Lecroq, Plandowski, Rytter Sequential Multiple String Matching ........................... 826 1999; Crochemore, Czumaj, Gqsieniec, Lecroq, Plandowski, Rytter Set Agreement ................................................. 829 1993; Chaudhuri Set Cover with Almost Consecutive Ones ........................ 832 2004;Mecke, Wagner Shortest Elapsed Time First Scheduling ........................ 834 2003; Bansal, Pruhs Shortest Paths Approaches for Timetable Information ........... 837 2004; Pyrga, Schulz, Wagner, Zaroliagis Shortest Paths in Planar Graphs with Negative Weight Edges .... 838 2001; Fakcharoenphol, Rao Shortest Vector Problem ....................................... 841 1982; Lenstra, Lenstra, Lovasz Similarity between Compressed Strings ......................... 843 2005; Kim, Amir, Landau, Park Single-Source Fully Dynamic Reachability ...................... 846 2005; Demetrescu, Italiano Single-Source Shortest Paths .................................. 847 1999; Thorup Ski Rental Problem ............................................ 849 1990; Karlin, Manasse, McGeogh, Owicki Slicing Floorplan Orientation ................................. 852 1983; Stockmeyer Snapshots in Shared Memory .................................... 855 1993; Afek, Attiya, Dolev, Gafni, Merritt, Shavit Sorting Signed Permutations by Reversal (Reversal Distance) ... 858 2001; Bader, Moret, Yan Sorting Signed Permutations by Reversal (Reversal Sequence) ... 860 2004; Tannier, Sagot Sorting by Transpositions and Reversals (Approximate Ratio 1.5) .......................................................... 863 2004; Hartman, Sharan Sparse Graph Spanners ......................................... 867 2004; Elkin, Peleg Sparsest Cut .................................................. 868 2004; Arora, Rao, Vazirani Speed Scaling ................................................. 870 1995; Yao, Demers, Shenker Sphere Packing Problem ........................................ 871 2001; Chen, Ни, Huang, Li, Xu Squares and Repetitions ....................................... 874 1999; Kolpakov, Kucherov Stable Marriage ............................................... 877 1962; Gale, Shapley Stable Marriage and Discrete Convex Analysis .................. 880 2000; Eguchi, Fujishige, Tamura, Fleiner Stable Marriage with Ties and Incomplete Lists ................ 883 2007; Iwama, Miyazaki, Yamauchi Stable Partition Problem ...................................... 885 2002; Cechlarova, Hajdukova Stackelberg Games: The Price of Optimum ....................... 888 2006; Kaporis, Spirakis Statistical Multiple Alignment ................................ 892 2003; Hein, Jensen, Pedersen Statistical Query Learning .................................... 894 1998; Kearns Steiner Forest ................................................ 897 1995; Agrawal, Klein, Ravi Steiner Trees ................................................. 900 2006; Du, Graham, Pardalos, Wan, Wu, Zhao Stochastic Scheduling ......................................... 904 2001; Glazebrook, Nino-Mora String Sorting ................................................ 907 1997; Bentley, Sedgewick Substring Parsimony ........................................... 910 2001; Blanchette, Schwikowski, Tompa Succinct Data Structures for Parentheses Matching ............. 912 2001; Munro, Raman Succinct Encoding of Permutations: Applications to Text Indexing ...................................................... 915 2003; Munro, Raman, Raman, Rao Suffix Array Construction ..................................... 919 2006; Karkkainen, Sanders, Burkhardt Suffix Tree Construction in Hierarchical Memory ............... 922 2000; Farach-Colton, Ferragina, Muthukrishnan Suffix Tree Construction in RAM ............................... 925 1997; Farach-Colton Support Vector Machines ....................................... 928 1992; Boser, Guy on, Vapnik Symbolic Model Checking ....................................... 932 1990; Burch, Clarke, McMillan, Dill Synchronizers, Spanners ....................................... 935 1985; Awerbuch Table Compression ............................................. 939 2003; Buchsbaum, Fowler, Giancarlo Tail Bounds for Occupancy Problems ............................ 942 1995; Kamath, Motwani, Palem, Spirakis Technology Mapping ............................................ 944 1987; Keutzer Teleportation of Quantum States ............................... 947 1993; Bennett, Brassard, Crepeau, Jozsa, Peres, Wootters Text Indexing ................................................. 950 1993; Manber, Myers Thresholds of Random k-Sat .................................... 954 2002; Kaporis, Kirousis, Lalas Topology Approach in Distributed Computing .................... 956 1999; Herlihy Shavit Trade-Offs for Dynamic Graph Problems ......................... 958 2005; Demetrescu, Italiano Traveling Sales Person with Few Inner Points .................. 961 2004; Deineko, Hoffmann, Okamoto, Woeginger Tree Compression and Indexing ................................. 964 2005; Ferragina, Luccio, Manzini, Muthukrishnan Treewidth of Graphs ........................................... 968 1987; Arnborg, Cornell, Proskurowski Truthful Mechanisms for One-Parameter Agents .................. 970 2001; Archer, Tardos Truthful Multicast ............................................ 973 2004; Wang, Li, Wang TSP-Based Curve Reconstruction ................................ 976 2001; Althaus, Mehlhorn Two-Dimensional Pattern Indexing .............................. 979 2005; Na, Giancarlo, Park Two-Dimensional Scaled Pattern Matching ....................... 982 2006; Amir, Chencinski Two-Interval Pattern Problems ................................. 985 2004; Vialette 2007; Cheng, Yang, Yuan Two-Level Boolean Minimization ................................ 989 1956; McCluskey Undirected Feedback Vertex Set ................................ 995 2005; Dehne, Fellows, Langston, Rosamond, Stevens; 2005; Guo, Gramm, Htiffner, Niedermeier, Wernicke Utilitarian Mechanism Design for Single-Minded Agents ......... 997 2005; Briest, Krysta, Vocking Vertex Cover Kernelization ................................... 1003 2004; Abu-Khzam, Collins, Fellows, Langston, Suters, Symons Vertex Cover Search Trees .................................... 1006 2001; Chen, Kan], Jia Visualization Techniques for Algorithm Engineering ........... 1008 2002; Demetrescu, Finocchi, Italiano, Naher Voltage Scheduling ........................................... 1011 2005; Li, Yao Wait-Free Synchronization .................................... 1015 1991;Herlihy Weighted Connected Dominating Set ............................ 1020 2005; Wang, Wang, Li Weighted Popular Matchings ................................... 1023 2006; Mestre Weighted Random Sampling ..................................... 1024 2005; Efraimidis, Spirakis Well Separated Pair Decomposition ............................ 1027 2003; Gao, Zhang Well Separated Pair Decomposition for Unit-Disk Graph ........ 1030 1995; Callahan, Kosaraju Wire Sizing .................................................. 1032 1999; Chu, Wong Work-Function Algorithm for к Servers ........................ 1035 1994; Koutsoupias, Papadimitriou Chronological Index .......................................... 1039 Bibliography ................................................. 1053 Index ........................................................ 1157