Yasuhito Asano, Yuya Miyawaki, Takao Nishizeki (auth.), Xiaodong Hu, Jie Wang (eds.)3540697322, 9783540697329
The refereed proceedings of the 14th Annual International Computing and Combinatorics Conference, COCOON 2008, held in Dalian, China, in June 2008.
The 66 revised full papers presented were carefully reviewed and selected from 172 submissions. The papers are organized in topical sections on algorithms and data structures, algorithmic game theory and online algorithms, automata, languages, logic, and computability, combinatorics related to algorithms and complexity, complexity theory, cryptography, reliability and security, and database theory, computational biology and bioinformatics, computational algebra, geometry, and number theory, graph drawing and information visualization, graph theory and algorithms, communication networks, and optimization, wireless network, network optimization, and scheduling problem.
Table of contents :
Front Matter….Pages –
Efficient Compression of Web Graphs….Pages 1-11
Damaged BZip Files Are Difficult to Repair….Pages 12-21
Isoperimetric Problem and Meta-fibonacci Sequences….Pages 22-30
On the Complexity of Equilibria Problems in Angel-Daemon Games….Pages 31-40
Average-Case Competitive Analyses for One-Way Trading….Pages 41-51
On the Monotonicity of Weak Searching….Pages 52-61
VC Dimension Bounds for Analytic Algebraic Computations….Pages 62-71
Resource Bounded Frequency Computations with Three Errors….Pages 72-81
A Sublinear Time Randomized Algorithm for Coset Enumeration in the Black Box Model….Pages 82-91
Smallest Formulas for Parity of 2 k Variables Are Essentially Unique….Pages 92-99
Counting Polycubes without the Dimensionality Curse….Pages 100-109
Polychromatic Colorings of n -Dimensional Guillotine-Partitions….Pages 110-118
The Computational Complexity of Link Building….Pages 119-129
Improved Parameterized Algorithms for Weighted 3-Set Packing….Pages 130-139
Structural Identifiability in Low-Rank Matrix Factorization….Pages 140-148
Complexity of Counting the Optimal Solutions….Pages 149-159
The Orbit Problem Is in the GapL Hierarchy….Pages 160-169
Quantum Separation of Local Search and Fixed Point Computation….Pages 170-179
Multi-party Quantum Communication Complexity with Routed Messages….Pages 180-190
Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments….Pages 191-203
Approximating Alternative Solutions….Pages 204-214
Dimensions of Points in Self-similar Fractals….Pages 215-224
Visual Cryptography on Graphs….Pages 225-234
Algebraic Cryptanalysis of CTRU Cryptosystem….Pages 235-244
Detecting Community Structure by Network Vectorization….Pages 245-254
Quasi-bicliques: Complexity and Binding Pairs….Pages 255-264
Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis….Pages 265-275
Genome Halving under DCJ Revisited….Pages 276-286
Haplotype Inferring Via Galled-Tree Networks Is NP-Complete….Pages 287-298
Adjacent Swaps on Strings….Pages 299-308
Efficient Algorithms for SNP Haplotype Block Selection Problems….Pages 309-318
Sequence Alignment Algorithms for Run-Length-Encoded Strings….Pages 319-330
A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations….Pages 331-341
A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI….Pages 342-351
Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance….Pages 352-362
On Center Regions and Balls Containing Many Points….Pages 363-373
On Unfolding 3D Lattice Polygons and 2D Orthogonal Trees….Pages 374-384
New Algorithms for Online Rectangle Filling with k -Lookahead….Pages 385-394
Geometric Spanner of Objects under L 1 Distance….Pages 395-404
Star-Shaped Drawings of Graphs with Fixed Embedding and Concave Corner Constraints….Pages 405-414
A New Characterization of P 6 -Free Graphs….Pages 415-424
Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction….Pages 425-433
Efficient Algorithms for the k Smallest Cuts Enumeration….Pages 434-443
Covering Directed Graphs by In-Trees….Pages 444-457
On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints….Pages 458-467
Probe Ptolemaic Graphs….Pages 468-477
Diagnosability of Two-Matching Composition Networks….Pages 478-486
The Iterated Restricted Immediate Snapshot Model….Pages 487-497
Finding Frequent Items in a Turnstile Data Stream….Pages 498-509
A Linear Programming Duality Approach to Analyzing Strictly Nonblocking d -ary Multilog Networks under General Crosstalk Constraints….Pages 510-520
Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost….Pages 521-530
Throughput Maximization with Traffic Profile in Wireless Mesh Network….Pages 531-540
Joint Topology Control and Power Conservation for Wireless Sensor Networks Using Transmit Power Adjustment….Pages 541-550
(6 + ε )-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs….Pages 551-557
Spectrum Bidding in Wireless Networks and Related….Pages 558-567
(1 + ρ )-Approximation for Selected-Internal Steiner Minimum Tree….Pages 568-576
Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities….Pages 577-586
Spreading Messages….Pages 587-599
On Some City Guarding Problems….Pages 600-610
Optimal Insertion of a Segment Highway in a City Metric….Pages 611-620
Approximating the Generalized Capacitated Tree-Routing Problem….Pages 621-630
Column Generation Algorithms for the Capacitated m -Ring-Star Problem….Pages 631-641
Two-Agent Scheduling with Linear Deteriorating Jobs on a Single Machine….Pages 642-650
A Two-Stage Flexible Flowshop Problem with Deterioration….Pages 651-660
A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm….Pages 661-669
The Coordination of Two Parallel Machines Scheduling and Batch Deliveries….Pages 670-677
Back Matter….Pages –
Reviews
There are no reviews yet.