+612 9045 4394
 
CHECKOUT
Computing and Combinatorics : 7th Annual International Conference, Cocoon 2001, Guilin, China, August 20-23, 2001, Proceedings - Jie Wang

Computing and Combinatorics

7th Annual International Conference, Cocoon 2001, Guilin, China, August 20-23, 2001, Proceedings

By: Jie Wang (Editor)

Paperback

Published: 3rd August 2001
Ships: 15 business days
15 business days
$181.29
or 4 easy payments of $45.32 with Learn more

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 ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Michal Kouck´ y On Universally Polynomial Context-Free Languages. . . . . . . . . . . . . . . . . . . . 21 Nicholas Tran Separating Oblivious and Non-oblivious BPs. . . . . . . . . . . . . . . . . . . . . . . . . . 28 Kazuo Iwama, Yasuo Okabe, Toshiro Takase Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws. . . 39 Iain A. Stewart Algebraic Properties for P-Selectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 LaneA. Hemaspaandra,HaraldHempel,ArfstNickelsen Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara ComputationalBiology Enhanced Sequence Reconstruction with DNA Microarray Application. . . . 64 Samuel A. Heath, Franco P. Preparata Non-approximability of Weighted Multiple Sequence Alignment. . . . . . . . . .

Complete Problems for Valiant's Class of qp-Computable Families of Polynomialsp. 1
Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n[superscript 4.03])p. 11
On Universally Polynomial Context-Free Languagesp. 21
Separating Oblivious and Non-oblivious BPsp. 28
Program Schemes, Queues, the Recursive Spectrum and Zero-One Lawsp. 39
Algebraic Properties for P-Selectivityp. 49
Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAMp. 59
Enhanced Sequence Reconstruction with DNA Microarray Applicationp. 64
Non-approximability of Weighted Multiple Sequence Alignmentp. 75
A Greedy Algorithm for Optimal Recombinationp. 86
Generating Well-Shaped d-dimensional Delaunay Meshesp. 91
Towards Compatible Triangulationsp. 101
An Improved Upper Bound on the Size of Planar Convex-Hullsp. 111
On the Planar Two-Watchtower Problemp. 121
Efficient Generation of Triconnected Plane Triangulationsp. 131
Packing Two Disks into a Polygonal Environmentp. 142
Maximum Red/Blue Interval Matching with Applicationsp. 150
Computing Farthest Neighbors on a Convex Polytopep. 159
Finding an Optimal Bridge between Two Polygonsp. 170
How Good Is Sink Insertion?p. 181
Polynomial Time Algorithms for Three-Label Point Labelingp. 191
Approximation Algorithms for the Watchman Route and Zookeeper's Problemsp. 201
PC-Trees vs. PQ-Treesp. 207
Stacks versus Dequesp. 218
Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequencesp. 228
Competitive Facility Location along a Highwayp. 237
Membership for Core of LP Games and Other Gamesp. 247
Strong Solutions to the Identification Problemp. 257
Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2[superscript m])p. 262
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithmsp. 268
Finding the Most Vital Node of a Shortest Pathp. 278
Algorithm for the Cost Edge-Coloring of Treesp. 288
Counting H-Colorings of Partial [kappa]-Treesp. 298
A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graphp. 308
Graph Separators: A Parameterized Viewp. 318
On Assigning Prefix Free Codes to the Vertices of a Graphp. 328
A New Measure of Edit Distance Between Labeled Treesp. 338
A Highly Efficient Algorithm to Determine Bicritical Graphsp. 349
Layered Drawings of Graphs with Crossing Constraintsp. 357
On the Validity of Hierarchical Decompositionsp. 368
Lower Bounds on the Minus Domination and [kappa]-Subdomination Numbersp. 375
Edge Connectivity vs Vertex Connectivity in Chordal Graphsp. 384
Changing the Diameter of Graph Productsp. 390
Plane Graphs with Acyclic Complexp. 395
On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphsp. 400
A Notion of Cross-Perfect Bipartite Graphsp. 409
Some Results on Orthogonal Factorizationsp. 414
Cluttered Orderings for the Complete Graphp. 420
Improved On-Line Stream Merging: From a Restricted to a General Settingp. 432
On-Line Deadline Scheduling on Multiple Resourcesp. 443
Competitive Online Scheduling with Level of Servicep. 453
On-Line Variable Sized Coveringp. 463
On Testing for Zero Polynomials by a Set of Points with Bounded Precisionp. 473
A Randomized Algorithm for Gossiping in Radio Networksp. 483
Deterministic Application of Grover's Quantum Search Algorithmp. 493
Random Instance Generation for MAX 3SATp. 502
The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Pointsp. 509
An FPTAS for Weight-Constrained Steiner Trees in Series-Parallel Graphsp. 519
Decidable Approximations on Generalized and Parameterized Discrete Timed Automatap. 529
Multiplicative Adaptive Algorithms for User Preference Retrievalp. 540
Parametric Scheduling for Network Constraintsp. 550
A Logical Framework for Knowledge Sharing in Multi-agent Systemsp. 561
A Lockout Avoidance Algorithm without Using Time-Stamps for the [kappa]-Exclusion Problemp. 571
Prefix-Free Languages and Initial Segments of Computably Enumerable Degreesp. 576
Weakly Computable Real Numbers and Total Computable Real Functionsp. 586
Turing Computability of a Nonlinear Schrodinger Propagatorp. 596
Author Indexp. 601
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540424949
ISBN-10: 3540424946
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 606
Published: 3rd August 2001
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.2
Weight (kg): 0.86