Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E. Moret(UniversityofNewMexico;chair) JackSnoeyink(UNC-ChapelHill) TableofContents ALENEX2002 OntheImplementationofMST-BasedHeuristicsfortheSteinerProblem inGraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 M. PoggideAragËao, R. F. Werneck(CatholicUniversityof RiodeJaneiro) ATime-SensitiveSystemforBlack-BoxCombinatorialOptimization . . . . . 16 V. Phan, P. Sumazin, S. Skiena(SUNYStonyBrook) ACompressedBreadth-FirstSearchforSatis?ability . . . . . . . . . . . . . . . . . . . 29 D. B. Motter, I. L. Markov(UniversityofMichigan) UsingMulti-levelGraphsforTimetableInformationinRailwaySystems . . 43 F. Schulz, D. Wagner(UniversityofKonstanz),C. Zaroliagis (UniversityofPatras) EvaluatingtheLocalRatioAlgorithmforDynamicStorageAllocation . . . 60 K. Pruhs(UniversityofPittsburgh),E. Wiewiora(Universityof California, SanDiego) An Experimental Study of Prefetching and Caching Algorithms for the WorldWideWeb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 M. Curcio, S. Leonardi, A. Vitaletti (Universit`adiRoma"LaSapienza") TheTreewidthofJavaPrograms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 J. Gustedt(LORIA&INRIALorraine),O. A. Mæhle, J. A. Telle (UniversityofBergen) PartitioningPlanarGraphswithCostsandWeights. . . . . . . . . . . . . . . . . . . . 98 L. Aleksandrov(BulgarianAcademyofSciences, CarletonUniversity), H. Djidjev(UniversityofWarwick),H. Guo, A. Maheshwari (CarletonUniversity) MaintainingDynamicMinimumSpanningTrees:AnExperimentalStudy . 111 G. Cattaneo, P. Faruolo, U. F. Petrillo(Universit`adiSalerno), G. F. Italiano(Universit`adiRoma"TorVergata") ExperimentalEvaluationofaNewShortestPathAlgorithm . . . . . . . . . . . . 126 S. Pettie, V. Ramachandran, S. Sridhar(UniversityofTexasatAustin) GettingMorefromOut-of-CoreColumnsort. . . . . . . . . . . . . . . . . . . . . . . . . . . 143 G. Chaudhry, T. H. Cormen(DartmouthCollege) VIII TableofContents TopologicalSweepinDegenerateCases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 E. Rafalin, D. Souvaine(TuftsUniversity),I. Streinu(SmithCollege) AccelerationofK-MeansandRelatedClusteringAlgorithms. . . . . . . . . . . . . 166 S. J. Phillips(AT&TLabs-Research) STAR-Tree:AnE?cientSelf-AdjustingIndexforMovingObjects . . . . . . . 178 C. M. Procopiuc(AT&TResearchLab),P. K. Agarwal (DukeUniversity),S. Har-Peled(UniversityofIllinois) AnImprovementonTreeSelectionSort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 J. Chen(BellLabsResearch, Beijing) AuthorIndex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 OntheImplementationofMST-Based HeuristicsfortheSteinerProbleminGraphs Marcus Poggi de AragË ao and Renato F. Werneck DepartmentofInformatics, CatholicUniversityofRiodeJaneiro, R. MarquËesdeSËao Vicente, 225, RiodeJaneiro, RJ, 22453-900, Brazil. poggi@inf. puc-rio. br, rwerneck@cs. princeton. edu Abstract. Someofthemostwidelyusedconstructiveheuristicsforthe Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine e?cient implem- tations of heuristics based on the classic algorithms by Prim, Kruskal, and Bor? uvka. | Algorithm Engineering and Experiments by David M. Mount, Paperback | Indigo Chapters