Вышла новая энциклопедия по алгоритмам. Объем впечатляет.
Думаю будет весьма полезна студентам. В предисловии это и сказано.
Хотя, возможно, я снова "валяю дурака" (как выражался тут на форуме один ХВ) давая имеющуюся уже у всех знатоков эту книгу?
Ming-Yang Kao (Ed.)
Encyclopedia of Algorithms
With 183 Figures and 38 Tables
With 4075 References for Further Reading 123
ISBN: 978-0-387-30162-4
The Encyclopedia of Algorithms aims to provide the researchers, students, and practitioners of algorithmic research with
a mechanism to efficiently and accurately find the names, definitions, key results, and further readings of important
algorithmic problems.
The work covers a wide range of algorithmic areas, and each algorithmic area is covered by a collection of entries.
An encyclopedia entry is an in-depth mini-survey of an algorithmic problem and is written by an expert researcher. The
entries for an algorithmic area are compiled by an area editor to survey the representative results in that area and can
form the core materials of a course in the area.
The Encyclopedia does not use the format of a conventional long survey for several reasons. A conventional survey
takes a handful of individuals too much time to write and is difficult to update. An encyclopedia entry contains the
same kinds of information as in a conventional survey, but an encyclopedia entry is much shorter and is much easier
for readers to absorb and for editors to update. Furthermore, an algorithmic area is surveyed by a collection of entries
which together provide a considerable amount of up-to-date information about the area, while the writing and updating
of the entries is distributed among multiple authors to speed up the work.
This reference work will be updated on a regular basis and will evolve towards primarily an Internet-based medium
to allow timely updates and fast search. If you have feedback regarding a particular entry, please feel free to communicate
directly with the author or the area editor of that entry. If you are interested in authoring an entry, please contact
a suitable area editor. If you have suggestions on how to improve the Encyclopedia as a whole, please contact me at
kao@northwestern.edu.
The credit of the Encyclopedia goes to the area editors, the entry authors, the entry reviewers, and the project editors
at Springer, including Jennifer Evans and Jennifer Carlson.
Вот содержание энциклопедии:
Table of Contents
AbelianHiddenSubgroupProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1995; Kitaev
AdaptivePartitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1986; Du, Pan, Shing
AdwordsPricing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2007; Bu, Deng, Qi
AlgorithmDC-Tree for kServersonTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1991; Chrobak, Larmore
AlgorithmicCooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1999; Schulman, Vazirani
2002; Boykin, Mor, Roychowdhury, Vatan, Vrijen
AlgorithmicMechanismDesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1999; Nisan, Ronen
AlgorithmsforSpannersinWeightedGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2003; Baswana, Sen
AllPairsShortestPathsinSparseGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2004; Pettie
AllPairsShortestPathsviaMatrixMultiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2002; Zwick
AlternativePerformanceMeasuresinOnlineAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2000; Koutsoupias, Papadimitriou
AnalyzingCacheMisses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2003;Mehlhorn, Sanders
ApplicationsofGeometricSpannerNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2002; Gudmundsson, Levcopoulos, Narasimhan, Smid
ApproximateDictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh
ApproximateRegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1995; Wu, Manber, Myers
VIII Table of Contents
ApproximateTandemRepeats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2001; Landau, Schmidt, Sokol
2003; Kolpakov, Kucherov
ApproximatingMetricSpacesbyTreeMetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1996; Bartal, Fakcharoenphol, Rao, Talwar
2004; Bartal, Fakcharoenphol, Rao, Talwar
ApproximationsofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2003; Lipton, Markakis,Mehta
2006; Daskalaskis,Mehta, Papadimitriou
2006; Kontogiannis, Panagopoulou, Spirakis
ApproximationSchemesforBinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1982; Karmarker, Karp
ApproximationSchemesforPlanarGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1983; Baker
1994; Baker
ArbitrageinFrictionalForeignExchangeMarket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2003; Cai, Deng
ArithmeticCodingforDataCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1994; Howard, Vitter
AssignmentProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1955; Kuhn
1957;Munkres
AsynchronousConsensusImpossibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1985; Fischer, Lynch, Paterson
AtomicBroadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1995; Cristian, Aghili, Strong, Dolev
Attribute-EfficientLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1987; Littlestone
AutomatedSearchTreeGeneration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2004; Gramm, Guo, Hüffner, Niedermeier
Backtracking Based k-SATAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2005; Paturi, Pudlák, Saks, Zane
BestResponseAlgorithmsforSelfishRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2005; Fotakis, Kontogiannis, Spirakis
Bidimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2004; Demaine, Fomin, Hajiaghayi, Thilikos
BinaryDecisionGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
1986; Bryant
Table of Contents IX
BinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1997; Coffman, Garay, Johnson
BoostingTextualCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2005; Ferragina, Giancarlo,Manzini, Sciortino
BranchwidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2003; Fomin, Thilikos
BroadcastinginGeometricRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2001; Dessmark, Pelc
B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
1972; Bayer,McCreight
Burrows–WheelerTransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
1994; Burrows,Wheeler
ByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
1980; Pease, Shostak, Lamport
Cache-ObliviousB-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2005; Bender, Demaine, Farach-Colton
Cache-ObliviousModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
1999; Frigo, Leiserson, Prokop, Ramachandran
Cache-ObliviousSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
1999; Frigo, Leiserson, Prokop, Ramachandran
CausalOrder,LogicalClocks,StateMachineReplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
1978; Lamport
CertificateComplexityandExactLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
1995; Hellerstein, Pilliapakkamnatt, Raghavan,Wilkins
ChannelAssignmentandRoutinginMulti-RadioWirelessMeshNetworks . . . . . . . . . . . . . . . . . . . 134
2005; Alicherry, Bhatia, Li
CircuitPartitioning:ANetwork-Flow-BasedBalancedMin-CutApproach . . . . . . . . . . . . . . . . . . . . 138
1994; Yang,Wong
CircuitPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
2000; Caldwell, Kahng, Markov
2002; Kennings,Markov
2006; Kennings, Vorwerk
CircuitRetiming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
1991; Leiserson, Saxe
CircuitRetiming:AnIncrementalApproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
2005; Zhou
X TableofContents
ClockSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
1994; Patt-Shamir, Rajsbaum
ClosestStringandSubstringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2002; Li, Ma, Wang
ClosestSubstring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
2005;Marx
ColorCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
1995; Alon, Yuster, Zwick
CommunicationinAdHocMobileNetworksUsingRandomWalks . . . . . . . . . . . . . . . . . . . . . . . . 161
2003; Chatzigiannakis, Nikoletseas, Spirakis
CompetitiveAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
2001; Goldberg, Hartline, Wright
2002; Fiat, Goldberg, Hartline, Karlin
ComplexityofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
2006; Chen, Deng
ComplexityofCore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
2001; Fang, Zhu, Cai, Deng
CompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2003; Kida, Matsumoto, Shibata, Takeda, Shinohara, Arikawa
CompressedSuffixArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
2003; Grossi, Gupta, Vitter
CompressedText Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
2005; Ferragina,Manzini
CompressingIntegerSequencesandSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
2000;Moffat, Stuiver
ComputingPureEquilibriaintheGameofParallelLinks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
2002; Fotakis, Kontogiannis, Koutsoupias, Mavronicolas, Spirakis
2003; Even-Dar, Kesselman,Mansour
2003; Feldman, Gairing, Lücking, Monien, Rode
ConcurrentProgramming,MutualExclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
1965; Dijkstra
ConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2003; Cheng, Huang, Li,Wu, Du
ConnectivityandFault-ToleranceinRandomRegularGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
2000; Nikoletseas, Palem, Spirakis, Yung
ConsensuswithPartialSynchrony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
1988; Dwork, Lynch, Stockmeyer
Table of Contents XI
ConstructingaGalledPhylogeneticNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
2006; Jansson, Nguyen, Sung
CPUTimePricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
2005; Deng, Huang, Li
CriticalRangeforWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
2004; Wan, Yi
CryptographicHardnessofLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
1994; Kearns, Valiant
CuckooHashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
2001; Pagh, Rodler
DataMigration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
2004; Khuller, Kim, Wan
DataReductionforDominationinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
2004; Alber, Fellows, Niedermeier
DecodingReed–SolomonCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
1999; Guruswami, Sudan
DecrementalAll-PairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
2004; Demetrescu, Italiano
Degree-BoundedPlanarSpannerwithLowWeight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
2005; Song, Li, Wang
Degree-BoundedTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
1994; Fürer, Raghavachari
DeterministicBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
2000; Chrobak, Ga˛sieniec, Rytter
DeterministicSearchingontheLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
1988; Baeza-Yates, Culberson, Rawlins
Dictionary-BasedDataCompression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
1977; Ziv, Lempel
DictionaryMatchingandIndexing(ExactandwithErrors) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
2004; Cole, Gottlieb, Lewenstein
DilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
2005; Ebbers-Baumann, Grüne, Karpinski, Klein, Kutz, Knauer, Lingas
DirectedPerfectPhylogeny(BinaryCharacters) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
1991; Gusfield
DirectRoutingAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
2006; Busch, Magdon-Ismail, Mavronicolas, Spirakis
XII Table of Contents
Distance-BasedPhylogenyReconstruction(Fast-Converging) . . . . . . . . . . . . . . . . . . . . . . . . 251
2003; King, Zhang, Zhou
Distance-BasedPhylogenyReconstruction(OptimalRadius) . . . . . . . . . . . . . . . . . . . . . . . . . 253
1999; Atteson
2005; Elias, Lagergren
DistributedAlgorithmsforMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
1983; Gallager, Humblet, Spira
DistributedVertexColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
2004; Finocchi, Panconesi, Silvestri
DynamicTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
2005; Tarjan,Werneck
EditDistanceUnderBlockOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
2000; Cormode, Paterson, Sahinalp, Vishkin
2000;Muthukrishnan, Sahinalp
EfficientMethodsforMultipleSequenceAlignmentwithGuaranteedErrorBounds . . . . . . . . . . . . . 267
1993; Gusfield
EngineeringAlgorithmsforComputationalBiology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
2002; Bader, Moret, Warnow
EngineeringAlgorithmsforLargeNetworkApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
2002; Schulz,Wagner, Zaroliagis
EngineeringGeometricAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
2004; Halperin
EquivalenceBetweenPriorityQueuesandSorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
2002; Thorup
EuclideanTravelingSalespersonProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
1998; Arora
ExactAlgorithmsforDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
2005; Fomin, Grandoni, Kratsch
ExactAlgorithmsforGeneralCNFSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
1998; Hirsch
2003; Schuler
ExactGraphColoringUsingInclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
2006; Björklund, Husfeldt
ExperimentalMethodsforAlgorithmAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
2001;McGeoch
ExternalSortingandPermuting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
1988; Aggarwal, Vitter
Table of Contents XIII
FacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
1997; Shmoys, Tardos, Aardal
FailureDetectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
1996; Chandra, Toueg
False-Name-ProofAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
2004; Yokoo, Sakurai, Matsubara
FastMinimalTriangulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
2005; Heggernes, Telle, Villanger
Fault-TolerantQuantumComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
1996; Shor, Aharonov, Ben-Or, Kitaev
FloorplanandPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
1994; Kajitani, Nakatake,Murata, Fujiyoshi
FlowTimeMinimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
2001; Becchetti, Leonardi,Marchetti-Spaccamela, Pruhs
FPGATechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
1992; Cong, Ding
FractionalPackingandCoveringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
1991; Plotkin, Shmoys, Tardos
1995; Plotkin, Shmoys, Tardos
FullyDynamicAllPairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
2004; Demetrescu, Italiano
FullyDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
2001; Holm, de Lichtenberg, Thorup
FullyDynamicConnectivity:UpperandLowerBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
2000; Thorup
FullyDynamicHigherConnectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
1997; Eppstein, Galil, Italiano, Nissenzweig
FullyDynamicHigherConnectivityforPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
1998; Eppstein, Galil, Italiano, Spencer
FullyDynamicMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
2000; Holm, de Lichtenberg, Thorup
FullyDynamicPlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
1999; Galil, Italiano, Sarnak
FullyDynamicTransitiveClosure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
1999; King
GateSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
2002; Sundararajan, Sapatnekar, Parhi
XIV Table of Contents
GeneralEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
2002; Deng, Papadimitriou, Safra
GeneralizedSteinerNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
2001; Jain
GeneralizedTwo-ServerProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
2006; Sitters, Stougie
GeneralizedVickreyAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
1995; Varian
GeographicRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
2003; Kuhn,Wattenhofer, Zollinger
GeometricDilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
2006; Dumitrescu, Ebbers-Baumann, Grüne, Klein, Knauer, Rote
GeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
2002; Gudmundsson, Levcopoulos, Narasimhan
Gomory–HuTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
2007; Bhalgat, Hariharan, Kavitha, Panigrahi
GraphBandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
1998; Feige
2000; Feige
GraphColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
1994; Karger, Motwani, Sudan
1998; Karger, Motwani, Sudan
GraphConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
1994; Khuller, Vishkin
GraphIsomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
1980;McKay
GreedyApproximationAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
2004; Ruan, Du, Jia, Wu, Li, Ko
GreedySet-CoverAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
1974–1979, Chvátal, Johnson, Lovász, Stein
HamiltonCyclesinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
2005; Efthymiou, Spirakis
HardnessofProperLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
1988; Pitt, Valiant
HighPerformanceAlgorithmEngineeringforLarge-scaleProblems . . . . . . . . . . . . . . . . . . . . . . . 387
2005; Bader
Table of Contents XV
Hospitals/ResidentsProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
1962; Gale, Shapley
ImplementationChallengeforShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
2006; Demetrescu, Goldberg, Johnson
ImplementationChallengeforTSPHeuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
2002; Johnson, McGeoch
ImplementingSharedRegistersinAsynchronousMessage-PassingSystems . . . . . . . . . . . . . . . 400
1995; Attiya, Bar-Noy, Dolev
IncentiveCompatibleSelection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
2006; Chen, Deng, Liu
IndependentSetsinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
2004; Nikoletseas, Raptopoulos, Spirakis
IndexedApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
2006; Chan, Lam, Sung, Tam, Wong
InductiveInference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
1983; Case, Smith
I/O-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
1988; Aggarwal, Vitter
KineticDataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
1999; Basch, Guibas, Hershberger
Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
1975; Ibarra, Kim
LearningwiththeAidofanOracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
1996; Bshouty, Cleve, Gavaldà, Kannan, Tamon
LearningAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
2000; Beimel, Bergadano, Bshouty, Kushilevitz, Varricchio
LearningConstant-DepthCircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
1993; Linial,Mansour, Nisan
LearningDNFFormulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
1997; Jackson
LearningHeavyFourierCoefficientsofBooleanFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
1989; Goldreich, Levin
LearningwithMaliciousNoise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
1993; Kearns, Li
LearningSignificantFourierCoefficientsoverFiniteAbelianGroups . . . . . . . . . . . . . . . . . . . . . . . 438
2003; Akavia, Goldwasser, Safra
XVI Table of Contents
LEDA:aLibraryofEfficientAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
1995;Mehlhorn, Näher
LeontiefEconomyEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
2005; Codenotti, Saberi, Varadarajan, Ye
2005; Ye
LinearityTesting/TestingHadamardCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
1990; Blum, Luby, Rubinfeld
Linearizability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
1990; Herlihy, Wing
ListDecodingnearCapacity:FoldedRSCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
2006; Guruswami, Rudra
ListScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
1966; Graham
LoadBalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
1994; Azar, Broder, Karlin
1997; Azar, Kalyanasundaram, Plotkin, Pruhs,Waarts
LocalAlignment(withAffineGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
1986; Altschul, Erickson
LocalAlignment(withConcaveGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
1988;Miller,Myers
LocalApproximationofCoveringandPackingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
2003–2006; Kuhn, Moscibroda, Nieberg, Wattenhofer
LocalComputationinUnstructuredRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
2005;Moscibroda,Wattenhofer
Local Search Algorithms for kSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
1999; Schöning
Local Search for K-mediansandFacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
2001; Arya, Garg, Khandekar,Meyerson,Munagala, Pandit LowerBoundsforDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 473
2004; P˘atra¸scu, Demaine
LowStretchSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
2005; Elkin, Emek, Spielman, Teng
LPDecoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
2002 and later; Feldman, Karger, Wainwright
MajorityEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
2003; Chen, Deng, Fang, Tian
Table of Contents XVII
MarketGamesandContentDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
2005;Mirrokni
MaxCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
1994; Goemans, Williamson
1995; Goemans, Williamson
MaximumAgreementSubtree(of2BinaryTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
1996; Cole, Hariharan
MaximumAgreementSubtree(of3orMoreTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
1995; Farach, Przytycka, Thorup
MaximumAgreementSupertree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
2005; Jansson, Ng, Sadakane, Sung
MaximumCompatibleTree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
2001; Ganapathy, Warnow
Maximum-DensitySegment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
1994; Huang
MaximumMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
2004;Mucha, Sankowski
Maximum-scoringSegmentwithLengthRestrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
2002; Lin, Jiang, Chao
MaximumTwo-Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
2004; Williams
MaxLeafSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
2005; Estivill-Castro, Fellows, Langston, Rosamond
MetricalTaskSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
1992; Borodin, Linial, Saks
MetricTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
1976; Christofides
MinimumBisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
1999; Feige, Krauthgamer
MinimumCongestionRedundantAssignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
2002; Fotakis, Spirakis
MinimumEnergyBroadcastinginWirelessGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . 526
2005; Ambühl
MinimumEnergyCostBroadcastinginWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
2001; Wan, Calinescu, Li, Frieder
MinimumFlowTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
1997; Leonardi, Raz
XVIII Table of Contents
MinimumGeometricSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
1999; Krznaric, Levcopoulos, Nilsson
Minimumk-ConnectedGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
2000; Czumaj, Lingas
MinimumMakespanonUnrelatedMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
1990; Lenstra, Shmoys, Tardos
MinimumSpanningTrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
2002; Pettie, Ramachandran
MinimumWeightedCompletionTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
1999; Afrati et al.
MinimumWeightTriangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
1998; Levcopoulos, Krznaric
MobileAgentsandExploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
1952; Shannon
MulticommodityFlow,Well-linkedTerminalsandRoutingProblems . . . . . . . . . . . . . . . . . . . . . . . 551
2005; Chekuri, Khanna, Shepherd
Multicut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
1993; Garg, Vazirani, Yannakakis
1996; Garg, Vazirani, Yannakakis
MultidimensionalCompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
2003; Amir, Landau, Sokol
MultidimensionalStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
1999; Kärkkäinen, Ukkonen
Multi-levelFeedbackQueues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
1968; Coffman, Kleinrock
MultipleUnitAuctionswithBudgetConstraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
2005; Borgs, Chayes, Immorlica, Mahdian, Saberi
2006; Abrams
MultiplexPCRforGapClosing(Whole-genomeAssembly) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
2002; Alon, Beigel, Kasif, Rudich, Sudakov
MultiwayCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
1998; Calinescu, Karloff, Rabani
NashEquilibriaandDominantStrategiesinRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
2005; Wang, Li, Chu
NearestNeighborInterchangeandRelatedDistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
1999; DasGupta, He, Jiang, Li, Tromp, Zhang
Table of Contents XIX
NegativeCyclesinWeightedDigraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
1994; Kavvadias, Pantziou, Spirakis, Zaroliagis
Non-approximabilityofBimatrixNashEquilibria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
2006; Chen, Deng, Teng
Non-sharedEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
1985; Day
Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
2006; Deng, Fang, Sun
ObliviousRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
2002; Räcke
ObstacleAvoidanceAlgorithmsinWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
2007; Powell, Nikoletseas
O(log log n)-competitiveBinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
2004; Demaine, Harmon, Iacono, Patrascu
OnlineIntervalColoring. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
1981; Kierstead, Trotter
OnlineListUpdate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
1985; Sleator, Tarjan
OnlinePagingandCaching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
1985–2002;multiple authors
OptimalProbabilisticSynchronousByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
1988; Feldman,Micali
OptimalStableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
1987; Irving, Leather, Gusfield
P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
2001; Stoica, Morris, Karger, Kaashoek, Balakrishnan
PacketRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616
1988; Leighton, Maggs, Rao
PacketSwitchinginMulti-QueueSwitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
2004; Azar, Richter; Albers, Schmidt
PacketSwitchinginSingleBuffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
2003; Bansal, Fleischer, Kimbrel,Mahdian, Schieber, Sviridenko
PACLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
1984; Valiant
PageRankAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
1998; Brin, Page
XX Table of Contents
Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
1985; Sleator, Tarjan, Fiat, Karp, Luby, McGeoch, Sleator, Young
1991; Sleator, Tarjan; Fiat, Karp, Luby, McGeoch, Sleator, Young
ParallelAlgorithmsforTwoProcessorsPrecedenceConstraintScheduling . . . . . . . . . . . . . . . . . . . 627
2003; Jung, Serna, Spirakis
ParallelConnectivityandMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
2001; Chong, Han, Lam
ParameterizedAlgorithmsforDrawingGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
2004; Dujmovic,Whitesides
ParameterizedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
1993; Baker
ParameterizedSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
2003; Szeider
PeptideDeNovoSequencingwithMS/MS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
2005;Ma, Zhang, Liang
PerceptronAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
1959; Rosenblatt
PerfectPhylogeny(BoundedNumberofStates) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
1997; Kannan, Warnow
PerfectPhylogenyHaplotyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
2005; Ding, Filkov, Gusfield
Performance-DrivenClustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
1993; Rajaraman, Wong
PhylogeneticTreeConstructionfromaDistanceMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
1989; Hein
PlanarGeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
2005; Bose, Smid, Gudmundsson
PlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
1976; Booth, Lueker
PointPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
2003; Ukkonen, Lemström, Mäkinen
PositionAuction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
2005; Varian
PredecessorSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
2006; P˘atra¸scu, Thorup
PriceofAnarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
2005; Koutsoupias
Table of Contents XXI
PriceofAnarchyforMachinesModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
2002; Czumaj, Vöcking
ProbabilisticDataForwardinginWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
2004; Chatzigiannakis, Dimitriou, Nikoletseas, Spirakis
QuantizationofMarkovChains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
2004; Szegedy
QuantumAlgorithmforCheckingMatrixIdentities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
2006; Buhrman, Spalek
QuantumAlgorithmfortheCollisionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
1998; Brassard, Hoyer, Tapp
QuantumAlgorithmfortheDiscreteLogarithmProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
1994; Shor
QuantumAlgorithmforElementDistinctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
2004; Ambainis
QuantumAlgorithmforFactoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
1994; Shor
QuantumAlgorithmforFindingTriangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
2005;Magniez, Santha, Szegedy
QuantumAlgorithmfortheParityProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
1985; Deutsch
QuantumAlgorithmsforClassGroupofaNumberField . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
2005; Hallgren
QuantumAlgorithmforSearchonGrids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
2005; Ambainis, Kempe, Rivosh
QuantumAlgorithmforSolvingthePell’sEquation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
2002; Hallgren
QuantumApproximation oftheJonesPolynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
2005; Aharonov, Jones, Landau
QuantumDenseCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
1992; Bennett, Wiesner
QuantumErrorCorrection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
1995; Shor
QuantumKeyDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
1984; Bennett, Brassard
1991; Ekert
QuantumSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
1996; Grover
XXII Table of Contents
Quorums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
1985; Garcia-Molina, Barbara
RadiocoloringinPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
2005; Fotakis, Nikoletseas, Papadopoulou, Spirakis
RandomizationinDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
1996; Chandra
RandomizedBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
1992; Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
RandomizedEnergyBalanceAlgorithmsinSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
2005; Leone, Nikoletseas, Rolim
RandomizedGossipinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
2001; Chrobak, Ga˛sieniec, Rytter
RandomizedMinimumSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
1995; Karger, Klein, Tarjan
RandomizedParallelApproximationstoMaxFlow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
1991; Serna, Spirakis
RandomizedRounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
1987; Raghavan, Thompson
RandomizedSearchingonRaysor theLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740
1993; Kao, Reif, Tate
RandomPlanted3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
2003; Flaxman
RankedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744
2005; Abraham, Irving, Kavitha, Mehlhorn
RankandSelectOperationsonBinaryStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
1974; Elias
Rate-MonotonicScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751
1973; Liu, Layland
RectilinearSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
2002; Zhou, Shenoy, Nicholls
RectilinearSteinerTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
2004; Zhou
Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761
1986; Lamport, Vitanyi, Awerbuch
RegularExpressionIndexing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
2002; Chan, Garofalakis, Rastogi
Table of Contents XXIII
RegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
2004; Navarro, Raffinot
ReinforcementLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771
1992; Watkins
Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
1990; Attiya, Bar-Noy, Dolev, Peleg, Reischuk
RNASecondaryStructureBoltzmannDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
2005;Miklós, Meyer, Nagy
RNASecondaryStructurePredictionIncludingPseudoknots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780
2004; Lyngsø
RNASecondaryStructurePredictionbyMinimumFreeEnergy . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
2006; Ogurtsov, Shabalina, Kondrashov, Roytberg
Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
1997; (Navigation) Blum, Raghavan, Schieber
1998; (Exploration) Deng, Kameda, Papadimitriou
2001; (Localization) Fleischer, Romanik, Schuierer, Trippen
RobustGeometricComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
2004; Li, Yap
Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
2003; Azar, Cohen, Fiat, Kaplan, Räcke
RoutinginGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
2003; Kuhn,Wattenhofer, Zhang, Zollinger
RoutinginRoadNetworkswithTransitNodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796
2007; Bast, Funke, Sanders, Schultes
R-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800
2004; Arge, de Berg, Haverkort, Yi
SchedulersforOptimisticRateBasedFlowControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803
2005; Fatourou, Mavronicolas, Spirakis
SchedulingwithEquipartition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
2000; Edmonds
SelfishUnsplittableFlows:AlgorithmsforPureEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
2005; Fotakis, Kontogiannis, Spirakis
Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812
1974; Dijkstra
SeparatorsinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815
1998; Leighton, Rao
1999; Leighton, Rao
XXIV Table of Contents
SequentialApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
2003; Crochemore, Landau, Ziv-Ukelson
2004; Fredriksson, Navarro
SequentialCircuitTechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820
1998; Pan, Liu
SequentialExactStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
1994; Crochemore, Czumaj, Ga˛sieniec, Jarominek, Lecroq, Plandowski, Rytter
SequentialMultipleStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
1999; Crochemore, Czumaj, G¸asieniec, Lecroq, Plandowski, Rytter
SetAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
1993; Chaudhuri
SetCoverwithAlmostConsecutiveOnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
2004;Mecke, Wagner
ShortestElapsedTimeFirstScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834
2003; Bansal, Pruhs
ShortestPathsApproachesforTimetableInformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837
2004; Pyrga, Schulz,Wagner, Zaroliagis
ShortestPathsinPlanarGraphswithNegativeWeightEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
2001; Fakcharoenphol, Rao
ShortestVectorProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841
1982; Lenstra, Lenstra, Lovasz
SimilaritybetweenCompressedStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
2005; Kim, Amir, Landau, Park
Single-SourceFullyDynamicReachability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846
2005; Demetrescu, Italiano
Single-SourceShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
1999; Thorup
SkiRentalProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849
1990; Karlin,Manasse,McGeogh, Owicki
SlicingFloorplanOrientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852
1983; Stockmeyer
SnapshotsinSharedMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855
1993; Afek, Attiya, Dolev, Gafni, Merritt, Shavit
SortingSignedPermutationsbyReversal(ReversalDistance) . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
2001; Bader, Moret, Yan
SortingSignedPermutationsbyReversal(ReversalSequence) . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
2004; Tannier, Sagot
Table of Contents XXV
SortingbyTranspositionsandReversals(ApproximateRatio1.5) . . . . . . . . . . . . . . . . . . . . . . . . . 863
2004; Hartman, Sharan
SparseGraphSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
2004; Elkin, Peleg
SparsestCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868
2004; Arora, Rao, Vazirani
SpeedScaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870
1995; Yao, Demers, Shenker
SpherePackingProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871
2001; Chen, Hu, Huang, Li, Xu
SquaresandRepetitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874
1999; Kolpakov, Kucherov
StableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877
1962; Gale, Shapley
StableMarriageandDiscreteConvexAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
2000; Eguchi, Fujishige, Tamura, Fleiner
StableMarriagewithTiesandIncompleteLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883
2007; Iwama, Miyazaki, Yamauchi
StablePartitionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
2002; Cechlárová, Hajduková
StackelbergGames:ThePriceofOptimum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888
2006; Kaporis, Spirakis
StatisticalMultipleAlignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892
2003; Hein, Jensen, Pedersen
StatisticalQueryLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894
1998; Kearns
SteinerForest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
1995; Agrawal, Klein, Ravi
SteinerTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900
2006; Du, Graham, Pardalos,Wan,Wu, Zhao
StochasticScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904
2001; Glazebrook, Nino-Mora
StringSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
1997; Bentley, Sedgewick
SubstringParsimony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
2001; Blanchette, Schwikowski, Tompa
XXVI Table of Contents
SuccinctDataStructuresforParenthesesMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
2001;Munro, Raman
SuccinctEncodingofPermutations:ApplicationstoText Indexing . . . . . . . . . . . . . . . . . . . . . . . . 915
2003;Munro, Raman, Raman, Rao
SuffixArrayConstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
2006; Kärkkäinen, Sanders, Burkhardt
SuffixTreeConstructioninHierarchicalMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
2000; Farach-Colton, Ferragina,Muthukrishnan
SuffixTreeConstructioninRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925
1997; Farach-Colton
SupportVectorMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928
1992; Boser, Guyon, Vapnik
SymbolicModelChecking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932
1990; Burch, Clarke,McMillan, Dill
Synchronizers,Spanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935
1985; Awerbuch
TableCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939
2003; Buchsbaum, Fowler, Giancarlo
TailBoundsforOccupancyProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942
1995; Kamath, Motwani, Palem, Spirakis
TechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944
1987; Keutzer
TeleportationofQuantumStates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947
1993; Bennett, Brassard, Crepeau, Jozsa, Peres,Wootters
Text Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950
1993;Manber, Myers
Thresholds of Randomk-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
2002; Kaporis, Kirousis, Lalas
TopologyApproach inDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
1999; Herlihy Shavit
Trade-OffsforDynamicGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958
2005; Demetrescu, Italiano
TravelingSalesPersonwithFewInnerPoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
2004; De˘ıneko, Hoffmann, Okamoto, Woeginger
TreeCompressionandIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964
2005; Ferragina, Luccio, Manzini,Muthukrishnan
Table of Contents XXVII
TreewidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968
1987; Arnborg, Corneil, Proskurowski
TruthfulMechanismsforOne-ParameterAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 970
2001; Archer, Tardos
TruthfulMulticast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
2004; Wang, Li, Wang
TSP-BasedCurveReconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 976
2001; Althaus, Mehlhorn
Two-DimensionalPatternIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979
2005; Na, Giancarlo, Park
Two-DimensionalScaledPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982
2006; Amir, Chencinski
Two-IntervalPatternProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985
2004; Vialette
2007; Cheng, Yang, Yuan
Two-LevelBooleanMinimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989
1956;McCluskey
UndirectedFeedbackVertexSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995
2005; Dehne, Fellows, Langston, Rosamond, Stevens;
2005; Guo, Gramm, Hüffner, Niedermeier,Wernicke
UtilitarianMechanismDesignforSingle-MindedAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997
2005; Briest, Krysta, Vöcking
VertexCoverKernelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1003
2004; Abu-Khzam, Collins, Fellows, Langston, Suters, Symons
VertexCoverSearchTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1006
2001; Chen, Kanj, Jia
VisualizationTechniquesforAlgorithmEngineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1008
2002; Demetrescu, Finocchi, Italiano, Näher
VoltageScheduling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1011
2005; Li, Yao
Wait-FreeSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015
1991; Herlihy
WeightedConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1020
2005; Wang,Wang, Li
WeightedPopularMatchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1023
2006;Mestre
XXVIII Table of Contents
WeightedRandomSampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1024
2005; Efraimidis, Spirakis
WellSeparatedPairDecomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1027
2003; Gao, Zhang
WellSeparatedPairDecompositionforUnit–DiskGraph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1030
1995; Callahan, Kosaraju
WireSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1032
1999; Chu, Wong
Work-FunctionAlgorithmforkServers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1035
1994; Koutsoupias, Papadimitriou
Chronological Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............................. . . 1039
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............................. . . . . . . 1053
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............................. . . . . . . . 1157
