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

Front Cover
Springer Science & Business Media, Jun 16, 2008 - Computers - 680 pages
The 14th Annual International Computing and Combinatorics Conference, CO- COON2008, tookplaceinDalian, China, June27-29,2008.PastCOCOONc- ferences were held in Xi'an (1995), Hong Kong (1996), Shanghai (1997), Taipei (1998), Tokyo (1999), Sydney (2000), Guilin (2001), Singapore (2002), Montana (2003), Jeju Island (2004), Kunming (2005), Taipei (2006), and Alberta (2007). COCOON 2008 provided a forum for researchers working in the areas of - gorithms, theory of computation, computational complexity, and combinatorics related to computing. The Program Committee received 172 submissions from 26 countries and regions: Canada, Australia, Austria, Brazil, China, Denmark, France, Germany, HongKong, Hungary, India, Iran, Israel, Japan, Korea, Mexico, Morocco, Netherlands, Pakistan, Singapore, Spain, Switzerland, Taiwan, Ukraine, the UK, and USA. With the help of 116 external referees, each submission was reviewed by at least two Program Committee members or external referees. Of the 172 subm- sions,66paperswereselectedforpresentationintheconferenceandareincluded in this volume. Some of these will be selected for publication in a special issue of Algorithmica and a special issue of the Journal of Combinatorial Optimization under the standard refereeing procedure. In addition to the selected papers, the conference also included two invited presentations by Der-Tsai Lee (Academia Sinica, Taiwan) and Takao Nishizeki (Tohoku University, Japan). The best paper awards were given for "Visual Cryptography on Graphs" to Lu, Manchala and Ostrovsky, and for "A Linear Programming Duality - proach to Analyzing Strictly Nonblocking d-ary Multilog Networks under G- eral Crosstalk Constraints" to Ngo, Wang and Le.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Efficient Compression of Web Graphs
1
Damaged BZip Files Are Difficult to Repair
12
Isoperimetric Problem and Metafibonacci Sequences
22
On the Complexity of Equilibria Problems in AngelDaemon Games
31
AverageCase Competitive Analyses for OneWay Trading
41
On the Monotonicity of Weak Searching
52
VC Dimension Bounds for Analytic Algebraic Computations
62
Resource Bounded Frequency Computations with Three Errors
72
Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance
352
On Center Regions and Balls Containing Many Points
363
On Unfolding 3D Lattice Polygons and 2D Orthogonal Trees
374
New Algorithms for Online Rectangle Filling with kLookahead
385
Geometric Spanner of Objects under L₁ Distance
395
StarShaped Drawings of Graphs with Fixed Embedding and Concave Corner Constraints
405
A New Characterization of P₆Free Graphs
415
Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
425

A Sublinear Time Randomized Algorithm for Coset Enumeration in the Black Box Model
82
Smallest Formulas for Parity of 2K Variables Are Essentially Unique
92
Counting Polycubes without the Dimensionality Curse
100
Polychromatic Colorings of nDimensional GuillotinePartitions
110
The Computational Complexity of Link Building
119
Improved Parameterized Algorithms for Weighted 3Set Packing
130
Structural Identifiability in LowRank Matrix Factorization
140
Complexity of Counting the Optimal Solutions
149
The Orbit Problem Is in the GapL Hierarchy
160
Quantum Separation of Local Search and Fixed Point Computation
170
Multiparty Quantum Communication Complexity with Routed Messages
180
Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments
191
Approximating Alternative Solutions
204
Dimensions of Points in Selfsimilar Fractals
215
Visual Cryptography on Graphs
225
Algebraic Cryptanalysis of CTRU Cryptosystem
235
Detecting Community Structure by Network Vectorization
245
Complexity and Binding Pairs
255
Complexity of a CollisionAware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
265
Genome Halving under DCJ Revisited
276
Haplotype Inferring Via GalledTree Networks Is NPComplete
287
Adjacent Swaps on Strings
299
Efficient Algorithms for SNP Haplotype Block Selection Problems
309
Sequence Alignment Algorithms for RunLengthEncoded Strings
319
A 225Approximation Algorithm for CutandPaste Sorting of Unsigned Circular Permutations
331
A Practical Exact Algorithm for the Individual Haplotyping Problem MECGI
342
Efficient Algorithms for the k Smallest Cuts Enumeration
434
Covering Directed Graphs by InTrees
444
On Listing Sampling and Counting the Chordal Graphs with Edge Constraints
458
Probe Ptolemaic Graphs
468
Diagnosability of TwoMatching Composition Networks
478
The Iterated Restricted Immediate Snapshot Model
487
Finding Frequent Items in a Turnstile Data Stream
498
A Linear Programming Duality Approach to Analyzing Strictly Nonblocking dary Multilog Networks under General Crosstalk Constraints
510
Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost
521
Throughput Maximization with Traffic Profile in Wireless Mesh Network
531
Joint Topology Control and Power Conservation for Wireless Sensor Networks Using Transmit Power Adjustment
541
6 + εApproximation for Minimum Weight Dominating Set in Unit Disk Graphs
551
Spectrum Bidding in Wireless Networks and Related
558
1 + ρApproximation for SelectedInternal Steiner Minimum Tree
568
Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
577
Spreading Messages
587
On Some City Guarding Problems
600
Optimal Insertion of a Segment Highway in a City Metric
611
Approximating the Generalized Capacitated TreeRouting Problem
621
TwoAgent Scheduling with Linear Deteriorating Jobs on a Single Machine
642
A TwoStage Flexible Flowshop Problem with Deterioration
651
A Lower Bound for the OnLine Preemptive Machine Scheduling with ℓᵨ Norm
661
The Coordination of Two Parallel Machines Scheduling and Batch Deliveries
670
Author Index
678
Copyright

Other editions - View all

Common terms and phrases