Buch, Englisch, Band 2108, 606 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1900 g
7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings
Buch, Englisch, Band 2108, 606 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1900 g
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-540-42494-9
Verlag: Springer Berlin Heidelberg
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.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
- Mathematik | Informatik EDV | Informatik Daten / Datenbanken Zeichen- und Zahlendarstellungen
- Mathematik | Informatik Mathematik Algebra Elementare Algebra
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik EDV | Informatik Informatik Künstliche Intelligenz Wissensbasierte Systeme, Expertensysteme
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Grafikprogrammierung
- Mathematik | Informatik Mathematik Operations Research Graphentheorie
Weitere Infos & Material
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.- Algorithm for the Cost Edge-Coloring of Trees.- Counting H-Colorings of Partial k-Trees.- A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph.- Graph Separators: A Parameterized View.- On Assigning Prefix Free Codes to the Vertices of a Graph.- A New Measure of Edit Distance between Labeled Trees.- A Highly Efficient Algorithm to Determine Bicritical Graphs.- Graph Drawing.- Layered Drawings of Graphs with Crossing Constraints.- On the Validity of Hierarchical Decompositions.- Graph Theory.- Lower Bounds on the Minus Domination and k-Subdomination Numbers.- Edge Connectivity vs Vertex Connectivity in Chordal Graphs.- Changing the Diameter of Graph Products.- Plane Graphs with Acyclic Complex.- On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs.- A Notion of Cross-Perfect Bipartite Graphs.- Some Results on Orthogonal Factorizations.- Cluttered Orderings for the Complete Graph.- Online Algorithms.- Improved On-Line Stream Merging: From a Restricted to a General Setting.- On-Line Deadline Scheduling on Multiple Resources.- Competitive Online Scheduling with Level of Service.- On-Line Variable Sized Covering.- Randomized and Average-Case Algorithms.- On Testing for Zero Polynomials by a Set of Points with Bounded Precision.- A Randomized Algorithm for Gossiping in Radio Networks.- Deterministic Application of Grover’s Quantum Search Algorithm.- Random Instance Generation for MAX 3SAT.- Steiner Trees.- The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points.- AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs.- SystemsAlgorithms and Modeling.- Decidable Approximations on Generalized and Parameterized Discrete Timed Automata.- Multiplicative Adaptive Algorithms for User Preference Retrieval.- Parametric Scheduling for Network Constraints.- A Logical Framework for Knowledge Sharing in Multi-agent Systems.- A Lockout Avoidance Algorithm without Using Time-Stamps for the k-Exclusion Problem.- Computability.- Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees.- Weakly Computable Real Numbers and Total Computable Real Functions.- Turing Computability of a Nonlinear Schrödinger Propagator.
