Computing and Combinatorics: 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings

Front Matter....Pages -
Derandomizing HSSW Algorithm for 3-SAT....Pages 1-12
Dominating Set Counting in Graph Classes....Pages 13-24
The Density Maximization Problem in Graphs....Pages 25-36
FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time....Pages 37-48
Tight Bounds on Local Search to Approximate the Maximum Satisfiability Problems....Pages 49-61
Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy....Pages 62-73
Exact Parameterized Multilinear Monomial Counting via k -Layer Subset Convolution and k -Disjoint Sum....Pages 74-85
On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms....Pages 86-97
On Parameterized Independent Feedback Vertex Set....Pages 98-109
Cograph Editing: Complexity and Parameterized Algorithms....Pages 110-121
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems....Pages 122-133
Strong I/O Lower Bounds for Binomial and FFT Computation Graphs....Pages 134-145
Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities....Pages 146-157
Quantum Algorithm for the Boolean Hidden Shift Problem....Pages 158-167
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability....Pages 168-179
Proper n -Cell Polycubes in n  − 3 Dimensions....Pages 180-191
Largest Area Convex Hull of Axis-Aligned Squares Based on Imprecise Data....Pages 192-203
Improved Algorithms for the Point-Set Embeddability Problem for Plane 3-Trees....Pages 204-212
Optimal Strategies for the One-Round Discrete Voronoi Game on a Line....Pages 213-224
Computing the Girth of a Planar Graph in Linear Time....Pages 225-236
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory....Pages 237-239
Unions of Disjoint NP-Complete Sets....Pages 240-251
ReachFewL = ReachUL....Pages 252-258
(1 +  ε )-Competitive Algorithm for Online OVSF Code Assignment with Resource Augmentation....Pages 259-270
Scheduling Jobs on Heterogeneous Platforms....Pages 271-283
Self-assembling Rulers for Approximating Generalized Sierpinski Carpets....Pages 284-296
Approximately Uniform Online Checkpointing....Pages 297-306
Bandwidth of Convex Bipartite Graphs and Related Graphs....Pages 307-318
Algorithms for Partition of Some Class of Graphs under Compaction....Pages 319-330
A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition....Pages 331-342
Matching and P 2 -Packing: Weighted Versions....Pages 343-353
On Totally Unimodularity of Edge-Edge Adjacency Matrices....Pages 354-365
The Topology Aware File Distribution Problem....Pages 366-378
Exploiting the Robustness on Power-Law Networks....Pages 379-390
Competitive Algorithms for Online Pricing....Pages 391-401
Making Abstraction-Refinement Efficient in Model Checking....Pages 402-413
An Integer Programming Approach for the Rural Postman Problem with Time Dependent Travel Times....Pages 414-431
Property Testing for Cyclic Groups and Beyond....Pages 432-443
Canonizing Hypergraphs under Abelian Group Action....Pages 444-455
Linear Time Algorithms for the Basis of Abelian Groups....Pages 456-466
Characterizations of Locally Testable Linear- and Affine-Invariant Families....Pages 467-478
A New Conditionally Anonymous Ring Signature....Pages 479-491
On the Right-Seed Array of a String....Pages 492-502
Compressed Directed Acyclic Word Graph with Application in Local Alignment....Pages 503-518
Unavoidable Regularities in Long Words with Bounded Number of Symbol Occurrences....Pages 519-530
Summing Symbols in Mutual Recurrences....Pages 531-542
Flipping Triangles and Rectangles....Pages 543-554
Unconstrained and Constrained Fault-Tolerant Resource Allocation....Pages 555-566
Finding Paths with Minimum Shared Edges....Pages 567-578
Combinatorial Group Testing for Corruption Localizing Hashing....Pages 579-591
Task Ordering and Memory Management Problem for Degree of Parallelism Estimation....Pages 592-603
Computing Majority with Triple Queries....Pages 604-615
A New Variation of Hat Guessing Games....Pages 616-626
Oblivious Transfer and n -Variate Linear Function Evaluation....Pages 627-637
Optimal Online Algorithms on Two Hierarchical Machines with Resource Augmentation....Pages 638-648
Back Matter....Pages -