Kao M.-Y. (ed.) Encyclopedia of Algorithms
Подождите немного. Документ загружается.
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
QuantumApproximationoftheJonesPolynomial .................................. 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, G ˛asieniec, Rytter
RandomizedMinimumSpanningTree .......................................... 732
1995; Karger, Klein, Tarjan
RandomizedParallelApproximationstoMaxFlow .................................. 734
1991; Serna, Spirakis
RandomizedRounding .................................................... 737
1987; Raghavan, Thompson
RandomizedSearchingonRaysortheLine ....................................... 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, G ˛asieniec, 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:ApplicationstoTextIndexing ........................ 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
TextIndexing .......................................................... 950
1993; Manber, Myers
Thresholds of Random k-S
AT ................................................. 954
2002; Kaporis, Kirousis, Lalas
TopologyApproachinDistributedComputing..................................... 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
ChronologicalIndex .......................................1039
Bibliography............................................1053
Index.................................................1157