Computing and Combinatorics: 14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008 Proceedings

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 -