Computing and Combinatorics

ThepapersinthisvolumewerepresentedattheSeventhAnnualInternational ComputingandCombinatoricsConference(COCOON2001),heldAugust20-23, 2001,inGuilin,China. Thetopicscovermostaspectsoftheoreticalcomputer scienceandcombinatoricsrelatedtocomputing. Theconferencewasheldin cooperationwiththeChineseAcademyofSciencesandChinaComputerFed- ation. Submissionstotheconferencethisyearwereconductedentirelyonline. A totalof97papersweresubmittedintimetobeconsidered,ofwhich50regular papersand16shortpaperswereselectedbyaninternationalprogramcommittee consistingofEricAllender,BernardChazelle,DannyChen,JianerChen,Francis Chin,Kyung-YongChwa,RodDowney,ErichGr adel,YuriGurevich,Steven Homer,ToshihideIbaraki,TaoJiang,Ker-IKo,D. T. Lee,XueminLin,Maurice Nivat,R. Ravi,Rudiger Reischuk,SeinosukeToda,JieWang,LushengWang, GuoliangXue,andMihalisYannakakis. Theauthorsofsubmittedpaperscomefromthefollowingcountriesand- gions:Australia,Austria,Bangladesh,Canada,China(includingHongKongand Taiwan),CzechRepublic,France,Germany,India,Israel,Italy,Japan,Korea, NewZealand,TheNetherlands,Poland,Russia,Singapore,Spain,Switzerland, U. K. ,andU. S. A. EachpaperwasgiventoatleastthreeProgramCommittee members,whoinsomecaseswereassistedbysubreferees. Inadditiontothe- lectedpapers,theconferencealsoincludedtwoinvitedpresentationsbyBernard ChazelleandAviWigderson. Topromoteyoungresearchers,theHaoWangAwardthisyearwasgiven toapaperselectedfrompaperswrittensolelybyauthorswho,atthetimeof submission,wereeitherstudentsorhadreceivedtheirdoctoraldegreeswithinthe previous?veyears. Iamhappytoannouncethattherecipientofthisawardwas Xiang-YangLiforhispaper GeneratingWell-Shapedd-DimensionalDelaunay Meshes . Iwouldliketothanktheprogramcommitteeco-chairYuriGurevichforhis strongsupportandallprogramcommitteemembers,theirsupportsta?,and subrefereesfortheirexcellentworkwithindemandingtimeconstraints. Iwould alsoliketothankallauthorsforsubmittingtheirpaperstotheconference. I amgratefultoSteveTateforlettingmeusetheACMSIGACTelectronics- missionservice,MinghuiLiforhelpingmecreateconferencewebpages,and RichardCheekforprovidingsystemsupport. Finally,Iwouldliketoexpressmy gratitudetoDing-ZhuDu,XudongHu,andalllocalorganizersfortheirhard workinmakingthismeetingpossibleandenjoyable. August2001 JieWang ProgramCommitteeChairs: YuriGurevich,MicrosoftResearch,USA JieWang,UniversityofMassachusettsLowell,USA ProgramCommitteeMembers: EricAllender,RutgersUniversity,USA BernardChazelle,PrincetonUniversity,USA DannyZ. Chen,UniversityofNotreDame,USA JianerChen,TexasA&MUniversity,USA FrancisChin,UniversityofHongKong,China Kyung-YongChwa,KoreaAdvancedInstituteofScience&Technology,Korea RodDowney,VictoriaUniversityofWellington,NewZealand ErichGr adel,AachenUniversityofTechnology,Germany StevenHomer,BostonUniversity,USA ToshihideIbaraki,KyotoUniversity,Japan TaoJiang,UniversityofCaliforniaatRiverside,USA Ker-IKo,StateUniversityofNewYorkatStonyBrook,USA D. T. Lee,AcademyofScience,Taiwan XueminLin,UniversityofNewSouthWales,Australia MauriceNivat,UniversityofParis,France R. Ravi,CarnegieMellonUniversity,USA R udigerReischuk,UniversityofLub eck,Germany SeinosukeToda,NihonUniversity,Japan LushengWang,CityUniversityofHongKong,China GuoliangXue,UniversityofVermont,USA MihalisYannakakis,BellLabs,USA Referees: DoritAharonov GuojunLi C. K. Poon KlausAmbos-Spies XueLi JohnShepherd DouglasBridges YanjunLi AmitabhSinha MarekChrobak YifanLi S. Skiena XiaotieDeng WeifaLiang MichaelTrick BjarniHalldorsson ShuangLuan KlausWagner PatrickHealy CatherineMcCartin C. A. Wang JohnHine AnilNerode WenpingWang YingpingHuang OjasParekh XiaodongWu XiaohuaJia Chong-DaePark BaogangXu Ming-YangKao Jung-HeumPark YuanshengYang JochenKonemann KunsooPark DongmoZhang TableofContents ComplexityTheory Complete Problems for Valiant s Class of qp-Computable Families of Polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Markus Bl aser Log-Space Constructible Universal Traversal Sequences 4. 03 for Cycles of LengthO(n ). . . . . . . . . . . .

Includes supplementary material: sn.pub/extras

Klappentext

strongsupportandallprogramcommitteemembers,theirsupportsta?,and subrefereesfortheirexcellentworkwithindemandingtimeconstraints. Iwould alsoliketothankallauthorsforsubmittingtheirpaperstotheconference. I amgratefultoSteveTateforlettingmeusetheACMSIGACTelectronics- missionservice,MinghuiLiforhelpingmecreateconferencewebpages,and RichardCheekforprovidingsystemsupport. Finally,Iwouldliketoexpressmy gratitudetoDing-ZhuDu,XudongHu,andalllocalorganizersfortheirhard workinmakingthismeetingpossibleandenjoyable. August2001 JieWang ProgramCommitteeChairs: YuriGurevich,MicrosoftResearch,USA JieWang,UniversityofMassachusettsLowell,USA ProgramCommitteeMembers: EricAllender,RutgersUniversity,USA BernardChazelle,PrincetonUniversity,USA DannyZ. Chen,UniversityofNotreDame,USA JianerChen,TexasA&MUniversity,USA FrancisChin,UniversityofHongKong,China Kyung-YongChwa,KoreaAdvancedInstituteofScience&Technology,Korea RodDowney,VictoriaUniversityofWellington,NewZealand ErichGradel,AachenUniversityofTechnology,Germany StevenHomer,BostonUniversity,USA ToshihideIbaraki,KyotoUniversity,Japan TaoJiang,UniversityofCaliforniaatRiverside,USA Ker-IKo,StateUniversityofNewYorkatStonyBrook,USA D. T. Lee,AcademyofScience,Taiwan XueminLin,UniversityofNewSouthWales,Australia MauriceNivat,UniversityofParis,France R. Ravi,CarnegieMellonUniversity,USA RudigerReischuk,UniversityofLub eck,Germany SeinosukeToda,NihonUniversity,Japan LushengWang,CityUniversityofHongKong,China GuoliangXue,UniversityofVermont,USA MihalisYannakakis,BellLabs,USA Referees: DoritAharonov GuojunLi C. K. Poon KlausAmbos-Spies XueLi JohnShepherd DouglasBridges YanjunLi AmitabhSinha MarekChrobak YifanLi S. Skiena XiaotieDeng WeifaLiang MichaelTrick BjarniHalldorsson ShuangLuan KlausWagner PatrickHealy CatherineMcCartin C. A. Wang JohnHine AnilNerode WenpingWang YingpingHuang OjasParekh XiaodongWu XiaohuaJia Chong-DaePark BaogangXu Ming-YangKao Jung-HeumPark YuanshengYang JochenKonemann KunsooPark DongmoZhang TableofConten

Inhalt
Complexity Theory.- Complete Problems for Valiant's Class of qp-Computable Families of Polynomials.- Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n 4.03).- On Universally Polynomial Context-Free Languages.- Separating Oblivious and Non-oblivious BPs.- Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws.- Algebraic Properties for P-Selectivity.- Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM.- Computational Biology.- Enhanced Sequence Reconstruction with DNA Microarray Application.- Non-approximability of Weighted Multiple Sequence Alignment.- A Greedy Algorithm for Optimal Recombination.- Computational Geometry.- Generating Well-Shaped d-dimensional Delaunay Meshes.- Towards Compatible Triangulations.- An Improved Upper Bound on the Size of Planar Convex-Hulls.- On the Planar Two-Watchtower Problem.- Efficient Generation of Triconnected Plane Triangulations.- Packing Two Disks into a Polygonal Environment.- Maximum Red/Blue Interval Matching with Application.- Computing Farthest Neighbors on a Convex Polytope.- Finding an Optimal Bridge between Two Polygons.- How Good Is Sink Insertion?.- Polynomial Time Algorithms for Three-Label Point Labeling.- Approximation Algorithms for the Watchman Route and Zookeeper's Problems.- Data Structures and Algorithms.- PC-Trees vs. PQ-Trees.- Stacks versus Deques.- Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences.- Games and Combinatorics.- Competitive Facility Location along a Highway.- Membership for Core of LP Games and Other Games.- Strong Solutions to the Identification Problem.- Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2m)1.- Graph Algorithms and Complexity.- A Space Saving Trick for DirectedDynamic Transitive Closure and Shortest Path Algorithms.- Finding the Most Vital Node of a Shortest Path.- Algorith…