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
|
