QQ截图未命名.bmp

Encyclopedia of Algorithms - Springer[2008]



Library of Congress Control Number: 2007933824
ISBN: 978-0-387-30162-4
This publication is available also as:
Print publication under ISBN: 978-0-387-30770-1 and
Print and electronic bundle under ISBN: 978-0-387-36061-4
© 2008 SpringerScience+BuisinessMedia, LLC.
All rights reserved. Thiswork may not be translated or copied inwhole or in partwithout the written permission of the publisher (Springer
Science+Business Media, LLC., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or
scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or
by similar or dissimilarmethodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to
be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
springer.com
Printed on acid free paper SPIN: 11563624 2109letex – 5 4 3 2 1 0

Preface
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.
Ming-Yang Kao
Editor-in-Chief

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
Minimum k-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

Ming-Yang Kao is a Professor of Computer Science in the Department of Electrical Engineering and Computer Science
at Northwestern University. He has published extensively in the design, analysis, and applications of algorithms. His
current interests include discrete optimization, bioinformatics, computational economics, computational finance, and
nanotechnology. He serves as the Editor-in-Chief of Algorithmica.
He obtained a B.S. in Mathematics from National Taiwan University in 1978 and a Ph.D. in Computer Science from
Yale University in 1986. He previously taught at Indiana University at Bloomington, Duke University, Yale University,
and Tufts University. At Northwestern University, he has served as the Department Chair of Computer Science. He
has also co-founded the Program in Computational Biology and Bioinformatics and served as its Director. He currently
serves as theHead of the EECS Division of Computing, Algorithms, and Applications and is amember of the Theoretical
Computer Science Group.
For more information please see: www.cs.northwestern.edu/~kao

List of Contributors
AARDAL, KAREN
CWI
Amsterdam
The Netherlands
Eindhoven University of Technology
Eindhoven
The Netherlands
AKAVIA, ADI
MIT
Cambridge, MA
USA
ALBERS, SUSANNE
University of Freiburg
Freiburg
Germany
ALICHERRY, MANSOOR
Bell Labs
Murray Hill, NJ
USA
ALON, NOGA
Tel-Aviv University
Tel-Aviv
Israel
ALTSCHUL, STEPHEN F.
The Rockefeller University
New York, NY
USA
MIT
Cambridge, MA
USA
ALURU, SRINIVAS
Iowa State University
Ames, IA
USA
AMBAINIS, ANDRIS
University of Latvia
Riga
Latvia
AMBÜHL, CHRISTOPH
University of Liverpool
Liverpool
UK
AMIR, AMIHOOD
Bar-Ilan University
Ramat-Gan
Israel
ASODI, VERA
California Institute of Technology
Pasadena, CA
USA
AUER, PETER
University of Leoben
Leoben
Austria
AZIZ, ADNAN
University of Texas
Austin, TX
USA
BABAIOFF, MOSHE
Microsoft Research, Silicon Valley
Mountain View, CA
USA
BADER, DAVID A.
Georgia Institute of Technology
Atlanta, GA
USA
BAEZA-YATES, RICARDO
University of Chile
Santiago
Chile
BANSAL, NIKHIL
IBM
Yorktown Heights, NY
USA
XXXVIII List of Contributors
BARBAY, JÉRÉMY
University of Chile
Santiago
Chile
BARUAH, SANJOY
University of North Carolina
Chapel Hill, NC
USA
BASWANA, SURENDER
IIT Kanpur
Kanpur
India
BECCHETTI, LUCA
University of Rome
Rome
Italy
BEIMEL, AMOS
Ben-Gurion University
Beer Sheva
Israel
BÉKÉSI, JÓZSEF
Juhász Gyula Teachers Training College
Szeged
Hungary
BERGADANO, FRANCESCO
University of Torino
Torino
Italy
BERRY, VINCENT
LIRMM, University of Montpellier
Montpellier
France
BHATIA, RANDEEP
Bell Labs
Murray Hill, NJ
USA
BJÖRKLUND, ANDREAS
Lund University
Lund
Sweden
BLANCHETTE, MATHIEU
McGill University
Montreal, QC
Canada
BLÄSER, MARKUS
Saarland University
Saarbrücken
Germany
BODLAENDER, HANS L.
University of Utrecht
Utrecht
The Netherlands
BORRADAILE, GLENCORA
Brown University
Providence, RI
USA
BSHOUTY, NADER H.
Technion
Haifa
Israel
BUCHSBAUM, ADAM L.
AT&T Labs, Inc.
Florham Park, NJ
USA
BUSCH, COSTAS
Lousiana State University
Baton Rouge, LA
USA
BU, TIAN-MING
Fudan University
Shanghai
China
BYRKA, JAROSLAW
CWI
Amsterdam
The Netherlands
Eindhoven University of Technology
Eindhoven
The Netherlands
CAI, MAO-CHENG
Chinese Academy of Sciences
Beijing
China
CALINESCU, GRUIA
Illinois Institute of Technology
Chicago, IL
USA
CECHLÁROVÁ, KATARÍNA
P.J. Šafárik University
Košice
Slovakia
List of Contributors XXXIX
CHAN, CHEE-YONG
National University of Singapore
Singapore
Singapore
CHANDRA, TUSHAR DEEPAK
IBM Watson Research Center
Yorktown Heights, NY
USA
CHAO, KUN-MAO
National Taiwan University
Taipei
Taiwan
CHARRON-BOST, BERNADETTE
The Polytechnic School
Palaiseau
France
CHATZIGIANNAKIS, IOANNIS
University of Patras and Computer Technology Institute
Patras
Greece
CHAWLA, SHUCHI
University of Wisconsin–Madison
Madison,WI
USA
CHEKURI, CHANDRA
University of Illinois, Urbana-Champaign
Urbana, IL
USA
CHEN, DANNY Z.
University of Notre Dame
Notre Dame, IN
USA
CHENG, XIUZHEN
The George Washington University
Washington, D.C.
USA
CHEN, JIANER
Texas A&M University
College Station, TX
USA
CHEN, XI
Tsinghua University
Beijing, Beijing
China
CHIN, FRANCIS
University of Hong Kong
Hong Kong
China
CHOWDHURY, REZAUL A.
University of Texas at Austin
Austin, TX
USA
CHRISTODOULOU, GEORGE
Max-Planck-Institute for Computer Science
Saarbruecken
Germany
CHROBAK, MAREK
University of California at Riverside
Riverside, CA
USA
CHU, CHRIS
Iowa State University
Ames, IA
USA
CHU, XIAOWEN
Hong Kong Baptist University
Hong Kong
China
CHUZHOY, JULIA
Toyota Technological Institute
Chicago, IL
USA
CONG, JASON
UCLA
Los Angeles, CA
USA
COWEN, LENORE J.
Tufts University
Medford, MA
USA
CRISTIANINI, NELLO
University of Bristol
Bristol
UK
CROCHEMORE, MAXIME
King’s College London
London
UK
University of Paris-East
Paris
France
XL List of Contributors
CS ˝URÖS, MIKLÓS
University of Montreal
Montreal, QC
Canada
CZUMAJ, ARTUR
University of Warwick
Coventry
UK
DASGUPTA, BHASKAR
University of Illinois at Chicago
Chicago, IL
USA
DÉFAGO, XAVIER
Japan Advanced Institute of Science and Technology
(JAIST)
Ishikawa
Japan
DEMAINE, ERIK D.
MIT
Cambridge, MA
USA
DEMETRESCU, CAMIL
University of Rome
Rome
Italy
DENG, PING
University of Texas at Dallas
Richardson, TX
USA
DENG, XIAOTIE
City University of Hong Kong
Hong Kong
China
DESPER, RICHARD
University College London
London
UK
DICK, ROBERT
Northwestern University
Evanston, IL
USA
DING, YUZHENG
Synopsys Inc.
Mountain View, CA
USA
DOM, MICHAEL
University of Jena
Jena
Germany
DUBHASHI, DEVDATT
Chalmers University of Technology and Gothenburg
University
Gothenburg
Sweden
DU, DING-ZHU
University of Dallas at Texas
Richardson, TX
USA
EDMONDS, JEFF
York University
Toronto, ON
Canada
EFRAIMIDIS, PAVLOS
Democritus University of Thrace
Xanthi
Greece
EFTHYMIOU, CHARILAOS
University of Patras
Patras
Greece
ELKIN, MICHAEL
Ben-Gurion University
Beer-Sheva
Israel
EPSTEIN, LEAH
University of Haifa
Haifa
Israel
ERICKSON, BRUCE W.
The Rockefeller University
New York, NY
USA
EVEN-DAR, EYAL
University of Pennsylvania
Philadelphia, PA
USA
FAGERBERG, ROLF
University of Southern Denmark
Odense
Denmark
List of Contributors XLI
FAKCHAROENPHOL, JITTAT
Kasetsart University
Bangkok
Thailand
FANG, QIZHI
Ocean University of China
Qingdao
China
FATOUROU, PANAGIOTA
University of Ioannina
Ioannina
Greece
FELDMAN, JONATHAN
Google, Inc.
New York, NY
USA
FELDMAN, VITALY
Harvard University
Cambridge, MA
USA
FERNAU, HENNING
University of Trier
Trier
Germany
FERRAGINA, PAOLO
University of Pisa
Pisa
Italy
FEUERSTEIN, ESTEBAN
University of Buenos Aires
Buenos Aires
Argentina
FISHER, NATHAN
University of North Carolina
Chapel Hill, NC
USA
FLAXMAN, ABRAHAM
Microsoft Research
Redmond, WA
USA
FLEISCHER, RUDOLF
Fudan University
Shanghai
China
FOMIN, FEDOR
University of Bergen
Bergen
Norway
FOTAKIS, DIMITRIS
University of the Aegean
Samos
Greece
FRIEDER, OPHIR
Illinois Institute of Technology
Chicago, IL
USA
FÜRER, MARTIN
The Pennsylvania State University
University Park, PA
USA
GAGIE, TRAVIS
University of Eastern Piedmont
Alessandria
Italy
GALAMBOS, GÁBOR
Juhász Gyula Teachers Training College
Szeged
Hungary
GAO, JIE
Stony Brook University
Stony Brook, NY
USA
GARAY, JUAN
Bell Labs
Murray Hill, NJ
USA
GAROFALAKIS, MINOS
University of California – Berkeley
Berkeley, CA
USA
GASCUEL, OLIVIER
National Scientific Research Center
Montpellier
France
GA˛SIENIEC, LESZEK
University of Liverpool
Liverpool
UK
XLII List of Contributors
GIANCARLO, RAFFAELE
University of Palermo
Palermo
Italy
GOLDBERG, ANDREW V.
Microsoft Research – Silicon Valley
Mountain View, CA
USA
GRAMM, JENS
Tübingen University
Tübingen
Germany
GROVER, LOV K.
Bell Labs
Murray Hill, NJ
USA
GUDMUNDSSON, JOACHIM
National ICT Australia Ltd
Alexandria
Australia
GUERRAOUI, RACHID
EPFL
Lausanne
Switzerland
GUO, JIONG
University of Jena
Jena
Germany
GURUSWAMI, VENKATESAN
University of Washington
Seattle,WA
USA
HAJIAGHAYI, MOHAMMADTAGHI
University of Pittsburgh
Pittsburgh, PA
USA
HALLGREN, SEAN
The Pennsylvania State University
University Park, PA
USA
HALPERIN, DAN
Tel-Aviv University
Tel Aviv
Israel
HARIHARAN, RAMESH
Strand Life Sciences
Bangalore
India
HELLERSTEIN, LISA
Polytechnic University
Brooklyn, NY
USA
HE, MENG
University ofWaterloo
Waterloo, ON
Canada
HENZINGER, MONIKA
Google Switzerland & Ecole Polytechnique Federale de
Lausanne (EPFL)
Lausanne
Switzerland
HERLIHY, MAURICE
Brown University
Providence, RI
USA
HERMAN, TED
University of Iowa
Iowa City, IA
USA
HE, XIN
University at Buffalo The State University of New York
Buffalo, NY
USA
HIRSCH, EDWARD A.
Steklov Institute of Mathematics at St. Petersburg
St. Petersburg
Russia
HON, WING-KAI
National Tsing Hua University
Hsin Chu
Taiwan
HOWARD, PAUL G.
Microway, Inc.
Plymouth, MA
USA
HUANG, LI-SHA
Tsinghua University
Beijing, Beijing
China
List of Contributors XLIII
HUANG, YAOCUN
University of Texas at Dallas
Richardson, TX
USA
HÜFFNER, FALK
University of Jena
Jena
Germany
HUSFELDT, THORE
Lund University
Lund
Sweden
ILIE, LUCIAN
University of Western Ontario
London, ON
Canada
IRVING, ROBERT W.
University of Glasgow
Glasgow
UK
ITAI, ALON
Technion
Haifa
Israel
ITALIANO, GIUSEPPE F.
University of Rome
Rome
Italy
IWAMA, KAZUO
Kyoto University
Kyoto
Japan
JACKSON, JEFFREY C.
Duquesne University
Pittsburgh, PA
USA
JACOB, RIKO
Technical University of Munich
Munich
Germany
JAIN, RAHUL
University ofWaterloo
Waterloo, ON
Canada
JANSSON, JESPER
Ochanomizu University
Tokyo
Japan
JIANG, TAO
University of California at Riverside
Riverside, CA
USA
JOHNSON, DAVID S.
AT&T Labs
Florham Park, NJ
USA
KAJITANI, YOJI
The University of Kitakyushu
Kitakyushu
Japan
KAPORIS, ALEXIS
University of Patras
Patras
Greece
KARAKOSTAS, GEORGE
McMaster University
Hamilton, ON
Canada
KÄRKKÄINEN, JUHA
University of Helsinki
Helsinki
Finland
KELLERER, HANS
University of Graz
Graz
Austria
KENNINGS, ANDREW A.
University ofWaterloo
Waterloo, ON
Canada
KEUTZER, KURT
University of California at Berkeley
Berkeley, CA
USA
KHULLER, SAMIR
University ofMaryland
College Park, MD
USA
XLIV List of Contributors
KIM, JINWOOK
HM Research
Seoul
Korea
KIM, YOO-AH
University of Connecticut
Storrs, CT
USA
KING, VALERIE
University of Victoria
Victoria, BC
Canada
KIROUSIS, LEFTERIS
University of Patras
Patras
Greece
KIVINEN, JYRKI
University of Helsinki
Helsinki
Finland
KLEIN, ROLF
University of Bonn
Bonn
Germany
KLIVANS, ADAM
University of Texas at Austin
Austin, TX
USA
KONJEVOD, GORAN
Arizona State University
Tempe, AZ
USA
KONTOGIANNIS, SPYROS
University of Ioannina
Ioannina
Greece
KRANAKIS, EVANGELOS
Carleton
Ottawa, ON
Canada
KRATSCH, DIETER
Paul Verlaine University
Metz
France
KRAUTHGAMER, ROBERT
Weizmann Institute of Science
Rehovot
Israel
IBM Almaden Research Center
San Jose, CA
USA
KRIZANC, DANNY
Wesleyan University
Middletown, CT
USA
KRYSTA, PIOTR
University of Liverpool
Liverpool
UK
KUCHEROV, GREGORY
LIFL and INRIA
Villeneuve d’Ascq
France
KUHN, FABIAN
ETH Zurich
Zurich
Switzerland
KUMAR, V.S.ANIL
Virginia Tech
Blacksburg, VA
USA
KUSHILEVITZ, EYAL
Technion
Haifa
Israel
LAM, TAK-WAH
University of Hong Kong
Hong Kong
China
LANCIA, GIUSEPPE
University of Udine
Udine
Italy
LANDAU, GAD M.
University of Haifa
Haifa
Israel
LANDAU, ZEPH
City College of CUNY
New York, NY
USA
List of Contributors XLV
LANGBERG, MICHAEL
The Open University of Israel
Raanana
Israel
LAVI, RON
Technion
Haifa
Israel
LECROQ, THIERRY
University of Rouen
Rouen
France
LEE, JAMES R.
University of Washington
Seattle,WA
USA
LEONARDI, STEFANO
University of Rome
Rome
Italy
LEONE, PIERRE
University of Geneva
Geneva
Switzerland
LEUNG, HENRY
MIT
Cambridge, MA
USA
LEVCOPOULOS, CHRISTOS
Lund University
Lund
Sweden
LEWENSTEIN, MOSHE
Bar-Ilan University
Ramat-Gan
Israel
LI, LI (ERRAN)
Bell Labs
Murray Hill, NJ
USA
LI, MING
University ofWaterloo
Waterloo, ON
Canada
LI, MINMING
City University of Hong Kong
Hong Kong
China
LINGAS, ANDRZEJ
Lund University
Lund
Sweden
LI, XIANG-YANG
Illinois Institue of Technology
Chicago, IL
USA
LU, CHIN LUNG
National Chiao Tung University
Hsinchu
Taiwan
LYNGSØ, RUNE B.
Oxford University
Oxford
UK
MA, BIN
University of Western Ontario
London, ON
Canada
MAHDIAN, MOHAMMAD
Yahoo! Research
Santa Clara, CA
USA
MÄKINEN, VELI
University of Helsinki
Helsinki
Finland
MALKHI, DAHLIA
Microsoft, Silicon Valley Campus
Mountain View, CA
USA
MANASSE, MARK S.
Microsoft Research
Mountain View, CA
USA
MANLOVE, DAVID F.
University of Glasgow
Glasgow
UK
XLVI List of Contributors
MANZINI, GIOVANNI
University of Eastern Piedmont
Alessandria
Italy
MARATHE, MADHAV V.
Virginia Tech
Blacksburg, VA
USA
MARCHETTI-SPACCAMELA, ALBERTO
University of Rome
Rome
Italy
MARKOV, IGOR L.
University of Michigan
Ann Arbor, MI
USA
MCGEOCH, CATHERINE C.
Amherst College
Amherst, MA
USA
MCGEOCH, LYLE A.
Amherst College
Amherst, MA
USA
MCKAY, BRENDAN D.
Australian National University
Canberra, ACT
Australia
MENDEL, MANOR
The Open University of Israel
Raanana
Israel
MESTRE, JULIÁN
University of Maryland
College Park, MD
USA
MICCIANCIO, DANIELE
University of California, San Diego
La Jolla, CA
USA
MIKLÓS, ISTVÁN
Eötvös Lóránd University
Budapest
Hungary
MIRROKNI, VAHAB S.
Microsoft Research
Redmond, WA
USA
MIYAZAKI, SHUICHI
Kyoto University
Kyoto
Japan
MOFFAT, ALISTAIR
University of Melbourne
Melbourne, VIC
Australia
MOIR, MARK
Sun Microsystems Laboratories
Burlington, MA
USA
MOR, TAL
Technion
Haifa
Israel
MOSCA, MICHELE
University ofWaterloo
Waterloo, ON
Canada
St. Jerome’s University
Waterloo, ON
Canada
MOSCIBRODA, THOMAS
Microsoft Research
Redmond, WA
USA
MUCHA, MARCIN
Institute of Informatics
Warsaw
Poland
MUNAGALA, KAMESH
Duke University
Durham, NC
USA
MUNRO, J. IAN
University ofWaterloo
Waterloo, ON
Canada
List of Contributors XLVII
NA, JOONG CHAE
Sejong University
Seoul
Korea
NARASIMHAN, GIRI
Florida International University
Miami, FL
USA
NAVARRO, GONZALO
University of Chile
Santiago
Chile
NAYAK, ASHWIN
University of Waterloo and Perimeter Institute for
Theoretical Physics
Waterloo, ON
Canada
NEWMAN, ALANTHA
Max-Planck Institute for Computer Science
Saarbrücken
Germany
NIEDERMEIER, ROLF
University of Jena
Jena
Germany
NIKOLETSEAS, SOTIRIS
University of Patras
Patras
Greece
OKAMOTO, YOSHIO
Toyohashi University of Technology
Toyohashi
Japan
OKUN, MICHAEL
Weizmann Institute of Science
Rehovot
Israel
PAGH, RASMUS
IT University of Copenhagen
Copenhagen
Denmark
PANAGOPOULOU, PANAGIOTA
Research Academic Computer Technology Institute
Patras
Greece
PANIGRAHI, DEBMALYA
MIT
Cambridge, MA
USA
PAN, PEICHEN
Magma Design Automation, Inc.
Los Angeles, CA
USA
PAPADOPOULOU, VICKY
University of Cyprus
Nicosia
Cyprus
PARK, KUNSOO
Seoul National University
Seoul
Korea
PARTHASARATHY, SRINIVASAN
IBM T.J. Watson Research Center
Hawthorne, NY
USA
P˘ATRA¸SCU, MIHAI
MIT
Cambridge, MA
USA
PATT-SHAMIR, BOAZ
Tel-Aviv University
Tel-Aviv
Israel
PATURI, RAMAMOHAN
University of California at San Diego
San Diego, CA
USA
PELC, ANDRZEJ
University of Québec-Ottawa
Gatineau, QC
Canada
PETTIE, SETH
University ofMichigan
Ann Arbor, MI
USA
POWELL, OLIVIER
University of Geneva
Geneva
Switzerland
XLVIII List of Contributors
PRAKASH, AMIT
Microsoft, MSN
Redmond, WA
USA
PRUHS, KIRK
University of Pittsburgh
Pittsburgh, PA
USA
PRZYTYCKA, TERESA M.
NIH
Bethesda,MD
USA
PUDLÁK, PAVEL
Academy of Science of the Czech Republic
Prague
Czech Republic
RAGHAVACHARI, BALAJI
University of Texas at Dallas
Richardson, TX
USA
RAHMAN, NAILA
University of Leicester
Leicester
UK
RAJARAMAN, RAJMOHAN
Northeastern University
Boston, MA
USA
RAJSBAUM, SERGIO
National Autonomous University of Mexico
Mexico City
Mexico
RAMACHANDRAN, VIJAYA
University of Texas at Austin
Austin, TX
USA
RAMAN, RAJEEV
University of Leicester
Leicester
UK
RAMOS, EDGAR
National University of Colombia
Medellín
Colombia
RAO, SATISH
University of California at Berkeley
Berkeley, CA
USA
RAO, S. SRINIVASA
IT University of Copenhagen
Copenhagen
Denmark
RAPTOPOULOS, CHRISTOFOROS
University of Patras
Patras
Greece
RASTOGI, RAJEEV
Lucent Technologies
Murray Hill, NJ
USA
RATSABY, JOEL
Ariel University Center of Samaria
Ariel
Israel
RAVINDRAN, KAUSHIK
University of California at Berkeley
Berkeley, CA
USA
RAYNAL, MICHEL
University of Rennes 1
Rennes
France
REICHARDT, BEN W.
California Institute of Technology
Pasadena, CA
USA
RENNER, RENATO
Institute for Theoretical Physics
Zurich
Switzerland
RICCI, ELISA
University of Perugia
Perugia
Italy
RICHTER, PETER
Rutgers, The State University of New Jersey
Piscataway, NJ
USA
List of Contributors XLIX
ROLIM, JOSÉ
University of Geneva
Geneva
Switzerland
ROSAMOND, FRANCES
University of Newcastle
Callaghan, NSW
Australia
RÖTTELER, MARTIN
NEC Laboratories America
Princeton, NJ
USA
RUBINFELD, RONITT
MIT
Cambridge, MA
USA
RUDRA, ATRI
University at Buffalo, State University of New York
Buffalo, NY
USA
RUPPERT, ERIC
York University
Toronto, ON
Canada
RYTTER, WOJCIECH
Warsaw University
Warsaw
Poland
SAHINALP, S. CENK
Simon Fraser University
Burnaby, BC
USA
SAKS, MICHAEL
Rutgers, State University of New Jersey
Piscataway, NJ
USA
SCHÄFER, GUIDO
Technical University of Berlin
Berlin
Germany
SCHIPER, ANDRÉ
EPFL
Lausanne
Switzerland
SCHMIDT, MARKUS
University of Freiburg
Freiburg
Germany
SCHULTES, DOMINIK
University of Karlsruhe
Karlsruhe
Germany
SEN, PRANAB
Tata Institute of Fundamental Research
Mumbai
India
SEN, SANDEEP
IIT Delhi
New Delhi
India
SERNA, MARIA
Technical University of Catalonia
Barcelona
Spain
SERVEDIO, ROCCO
Columbia University
New York, NY
USA
SETHURAMAN, JAY
Columbia University
New York, NY
USA
SHALEV-SHWARTZ, SHAI
Toyota Technological Institute
Chicago, IL
USA
SHARMA, VIKRAM
New York University
New York, NY
USA
SHI, YAOYUN
University ofMichigan
Ann Arbor, MI
USA
SHRAGOWITZ, EUGENE
University of Minnesota
Minneapolis, MN
USA
L List of Contributors
SITTERS, RENÉ A.
Eindhoven University of Technology
Eindhoven
The Netherlands
SMID, MICHIEL
Carleton University
Ottawa, ON
Canada
SOKOL, DINA
Brooklyn College of CUNY
Brooklyn, NY
USA
SONG, WEN-ZHAN
Washington State University
Vancouver,WA
USA
SPECKMANN, BETTINA
Technical University of Eindhoven
Eindhoven
The Netherlands
SPIRAKIS, PAUL
Patras University
Patras
Greece
SRINIVASAN, ARAVIND
University of Maryland
College Park, MD
USA
SRINIVASAN, VENKATESH
University of Victoria
Victoria, BC
Canada
STEE, ROB VAN
University of Karlsruhe
Karlsruhe
Germany
STØLTING BRODAL, GERTH
University of Aarhus
Århus
Denmark
STOYE, JENS
University of Bielefeld
Bielefeld
Germany
SU, CHANG
University of Liverpool
Liverpool
UK
SUN, ARIESWEI
City University of Hong Kong
Hong Kong
China
SUNDARARAJAN, VIJAY
Texas Instruments
Dallas, TX
USA
SUNG, WING-KIN
National University of Singapore
Singapore
Singapore
SVIRIDENKO, MAXIM
IBM
Yorktown Heights, NY
USA
SZEGEDY, MARIO
Rutgers, The State University of New Jersey
Piscataway, NJ
USA
SZEIDER, STEFAN
Durham University
Durham
UK
TAKAOKA, TADAO
University of Canterbury
Christchurch
New Zealand
TAKEDA, MASAYUKI
Kyushu University
Fukuoka
Japan
TALWAR, KUNAL
Microsoft Research, Silicon Valley Campus
Mountain View, CA
USA
TAMON, CHRISTINO
Clarkson University
Potsdam, NY
USA
List of Contributors LI
TAMURA, AKIHISA
Keio University
Yokohama
Japan
TANNIER, ERIC
University of Lyon
Lyon
France
TAPP, ALAIN
University ofMontréal
Montreal, QC
Canada
TATE, STEPHEN R.
University of North Carolina at Greensboro
Greensboro, NC
USA
TAUBENFELD, GADI
Interdiciplinary Center Herzlia
Herzliya
Israel
TELIKEPALLI, KAVITHA
Indian Institute of Science
Bangalore
India
TERHAL, BARBARA M.
IBM Research
Yorktown Heights, NY
USA
THILIKOS, DIMITRIOS
National and Kapodistrian University of Athens
Athens
Greece
TREVISAN, LUCA
University of California at Berkeley
Berkeley, CA
USA
TROMP, JOHN
CWI
Amsterdam
Netherlands
UKKONEN, ESKO
University of Helsinki
Helsinki
Finland
VAHRENHOLD, JAN
Dortmund University of Technology
Dortmund
Germany
VARRICCHIO, STEFANO
University of Roma
Rome
Italy
VIALETTE, STÉPHANE
University of Paris-East
Descartes
France
VILLANGER, YNGVE
University of Bergen
Bergen
Norway
VITÁNYI, PAUL
CWI
Amsterdam
Netherlands
VITTER, JEFFREY SCOTT
Purdue University
West Lafayette, IN
USA
VÖCKING, BERTHOLD
RWTH Aachen University
Aachen
Germany
WANG, CHENGWEN CHRIS
Carnegie Mellon University
Pittsburgh, PA
USA
WANG, FENG
Arizona State University
Phoenix, AZ
USA
WANG, LUSHENG
City University of Hong Kong
Hong Kong
China
WANG, WEIZHAO
Google Inc.
Irvine, CA
USA
LII List of Contributors
WANG, YU
University of North Carolina at Charlotte
Charlotte, NC
USA
WAN, PENG-JUN
Illinois Institute of Technology
Chicago, IL
USA
WERNECK, RENATO F.
Microsoft Research Silicon Valley
La Avenida, CA
USA
WILLIAMS, RYAN
Carnegie Mellon University
Pittsburgh, PA
USA
WONG, MARTIN D. F.
University of Illinois at Urbana-Champaign
Urbana, IL
USA
WONG, PRUDENCE
University of Liverpool
Liverpool
UK
WU, WEILI
University of Texas at Dallas
Richardson, TX
USA
YANG, HONGHUA HANNAH
Intel Corporation
Hillsboro
USA
YAP, CHEE K.
New York University
New York, NY
USA
YE, YIN-YU
Stanford University
Stanford, CA
USA
YI, CHIH-WEI
National Chiao Tung University
Hsinchu City
Taiwan
YI, KE
Hong Kong University of Science and Technology
Hong Kong
China
YIU, S. M.
The University of Hong Kong
Hong Kong
China
YOKOO, MAKOTO
Kyushu University
Nishi-ku
Japan
YOUNG, EVANGELINE F. Y.
The Chinese University of Hong Kong
Hong Kong
China
YOUNG, NEAL E.
University of California at Riverside
Riverside, CA
USA
YUSTER, RAPHAEL
University of Haifa
Haifa
Israel
ZANE, FRANCIS
Lucent Technologies
Murray Hill, NJ
USA
ZAROLIAGIS, CHRISTOS
University of Patras
Patras
Greece
ZEH, NORBERT
Dalhousie University
Halifax, NS
Canada
ZHANG, LI
HP Labs
Palo Alto, CA
USA
ZHANG, LOUXIN
National University of Singapore
Singapore
Singapore
List of Contributors LIII
ZHOU, HAI
Northwestern University
Evanston, IL
USA
ZILLES, SANDRA
University of Alberta
Edmonton, AB
Canada
ZOLLINGER, AARON
University of California at Berkeley
Berkeley, CA
USA
ZWICK, URI
Tel-Aviv University
Tel-Aviv
Israel

:11bb

:11bb

:11bb
[hide]
[/hide]

搞算法的，相信这本书应该是个值得收藏的经典书籍

如此好书，不顶都没天理了:11bb

支持一下

多谢楼主分享。。。
看一看。。。。

哇塞，这么多牛人啊，在这个牛群面前，感到了自己是多么的渺小，大家要努力争取早日挤进牛群啊！

对了，忘了谢谢楼主，哈哈:27bb:30bb

搞算法的，相信这本书应该是个值得收藏的经典书籍

如此好书，不顶都没天理了:11bb

好书 顶：17de ：17de ：17de ：17de ：17de

这样的书挺有意思的
:11bb

如此好书，不顶都没天理了，非常感谢

如此好书！支持！

我怎么感觉好像以前发过一样呢，还是说以前发过类似的

:11bb :11bb :11bb

强烈支持楼主！
祝广大坛友们新年好运！

感谢楼主分享
:11bb :11bb :11bb :11bb

好像在论坛里下过得很眼熟啊:yi

还有这么好的算法集合书籍呀！非常感谢版主00d44！！:11bb :30bb :27bb

What is it about?thank you

好书要支持

很好的资料，非常感谢楼主的共享！！！

算法的大百科全书啊，经典

:11bb :27bb :29bb

顶一个:11bb :11bb :11bb :11bb :11bb

想看看，赚积分，先谢谢了，thinks

顶!好书!:11bb :27bb :30bb

:11bb :11bb :11bb :11bb

eeeeeeeeeeeeeeeeeeeeeeeeeee

版主，十分佩服你，有这么多好资源:11bb :11bb :11bb

好书呀，支持支持，不过也只能当字典用了！

:27bb :27bb :27bb :27bb 如此好书，不顶都没天理了

好资料，想看看，呵呵，谢谢分享！

:30bb 想学习用，太需要了！

谢谢分享  这本书应该是个值得收藏的经典书籍

看样子很不错啊    :11bb :11bb ，挺好的

相信这本书应该是个值得收藏的经典书籍

：23de :31bb :11bb :27bb :27bb :29bb

好书，谢谢楼主分享。。。。。。。我为人人，人人为我！！

谢谢。。。。。。。。。。。

顶。。。。。。。。。

:11bb :11bb :11bb :11bb :11bb

:27bb 感觉怎么需要学习一下算法 了~

好资料啊,谢谢楼主了!

顶。。。。。。。。。。。。。。。。。。。。

:22bb:21bb:23bb

:27bb 17# 00d44

好东西！多谢

haoshu顶！！！

相信这本书应该是个值得收藏的经典书籍:31bb

谢谢你啊 ！！！！！！！！！！！
信息来源：微网社区-微波技术门户网站 http://bbs.mwtee.com
原文链接：http://bbs.mwtee.com/thread-15891-1-1.html

顶一个。。。。。。。。。。。。。。。。。。。。。。。

这么好的书，难得顶一下，:21bb

good!:27bb

相当不错呀：9de

我也支持一下吧

好书 谢谢 收了

这书太棒了  狂顶啊 谢谢楼主

谢谢楼主！！！:53bb:53bb

thx for sharing dude

值得收藏的经典书籍

:55bb:53bb.................

又是Springer！楼主真厉害！

:56bb.............

全英文的
有些难呀

excellent book

感谢楼主的无私奉献
辛苦

Wonderful! Well done! Thank you very much!

这本书很棒，把这么多算法都介绍了

专注，一定要支持！！！！！！！！

搞算法的，相信这本书应该是个值得收藏的经典书籍

太经典了！

必须看看，都称Encycopedia 了

{:7_1242:}

经典好书，心中的圣经

下载看看！！！！！

O(∩_∩)O哈哈~

经典之作，多谢楼主！
如此好书，精！

刚搞这个  感谢分享

了解一下            {:7_1249:}

这个仅作为收藏，谢谢

支持下{:7_1236:}

支持一下{:7_1234:}

:45bb谢谢楼主

谢谢分享好书

先谢谢啊{:7_1235:}{:7_1235:}{:7_1235:}

顶一下！！！！

值得收藏的经典书籍！！

好书，谢谢楼主。。。

感謝分享！{:soso_e100:}

感謝分享！{:soso_e100:}

谢谢分享！

真是本好书啊，多谢啦

鹅鹅鹅

我回复乐乐乐乐乐乐乐乐乐了

Good Book

相当不错谢谢分享

相当不错谢谢分享