Computing and Combinatorics: 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings

Front Matter....Pages -
Building above Read-once Polynomials: Identity Testing and Hardness of Representation....Pages 1-12
Sampling from Dense Streams without Penalty....Pages 13-24
 L  ∞  -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains....Pages 25-36
Sampling Query Feedback Restricted Repairs of Functional Dependency Violations: Complexity and Algorithm....Pages 37-48
Online Prediction Problems with Variation....Pages 49-60
Nondeterministic Automatic Complexity of Almost Square-Free and Strongly Cube-Free Words....Pages 61-70
An Axiomatization for Cylinder Computation Model....Pages 71-83
Normal Form Expressions of Propositional Projection Temporal Logic....Pages 84-93
On the Smoothed Heights of Trie and Patricia Index Trees....Pages 94-103
One-Dimensional k -Center on Uncertain Data....Pages 104-115
The Range 1 Query (R1Q) Problem....Pages 116-128
Competitive Cost-Savings in Data Stream Management Systems....Pages 129-140
On the Kernelization Complexity of String Problems....Pages 141-153
Complexity of Dense Bicluster Editing Problems....Pages 154-165
Parameterized Complexity of Edge Interdiction Problems....Pages 166-178
Vertex Cover Gets Faster and Harder on Low Degree Graphs....Pages 179-190
A Protocol for Generating Random Elements with Their Probabilities....Pages 191-202
A New View on Worst-Case to Average-Case Reductions for NP Problems....Pages 203-214
The Power of Duples (in Self-Assembly): It’s Not So Hip to Be Square....Pages 215-226
A Lin-Kernighan Heuristic for the DCJ Median Problem of Genomes with Unequal Contents....Pages 227-238
Diffuse Reflection Radius in a Simple Polygon....Pages 239-250
On Edge-Unfolding One-Layer Lattice Polyhedra with Cubic Holes....Pages 251-262
Directed Steiner Tree with Branching Constraint....Pages 263-275
On the Parameterized Complexity of Labelled Correlation Clustering Problem....Pages 276-287
Shortest Color-Spanning Intervals....Pages 288-299
Fixed Parameter Tractable Algorithms in Combinatorial Topology....Pages 300-311
Improved Approximation Algorithms for a Bilevel Knapsack Problem....Pages 312-323
A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem....Pages 324-335
Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties....Pages 336-345
A New Approximation Algorithm for the Unbalanced Min s - t Cut Problem....Pages 346-356
Approximability of the Minimum Weighted Doubly Resolving Set Problem....Pages 357-368
Approximating High-Dimensional Range Queries with k NN Indexing Techniques....Pages 369-380
Approximation Algorithms for Maximum Agreement Forest on Multiple Trees....Pages 381-392
Optimal Inspection Points for Malicious Attack Detection in Smart Grids....Pages 393-404
Reconfiguration of Dominating Sets....Pages 405-416
Back-Up 2-Center on a Path/Tree/Cycle/Unicycle....Pages 417-428
Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs....Pages 429-440
Approximation Algorithm for the Balanced 2-Connected Bipartition Problem....Pages 441-452
Improved Approximation for Time-Dependent Shortest Paths....Pages 453-464
Approximate Sorting of Data Streams with Limited Storage....Pages 465-476
Simpler Algorithms for Testing Two-Page Book Embedding of Partitioned Graphs....Pages 477-488
Classifying the Clique-Width of H -Free Bipartite Graphs....Pages 489-500
Displacing Random Sensors to Avoid Interference....Pages 501-512
On the Performance of Mildly Greedy Players in Cut Games....Pages 513-524
Statistical Properties of Short RSA Distribution and Their Cryptographic Applications....Pages 525-536
Numerical Tic-Tac-Toe on the 4×4 Board....Pages 537-546
On Linear Congestion Games with Altruistic Social Context....Pages 547-558
Scheduling over Scenarios on Two Machines....Pages 559-571
The Complexity of Bounded Register and Skew Arithmetic Computation....Pages 572-583
Minimizing Average Flow-Time under Knapsack Constraint....Pages 584-595
Depth Lower Bounds against Circuits with Sparse Orientation....Pages 596-607
Efficient Respondents Selection for Biased Survey Using Online Social Networks....Pages 608-615
Explaining Snapshots of Network Diffusions: Structural and Hardness Results....Pages 616-625
Pioneers of Influence Propagation in Social Networks....Pages 626-636
Empirical Models for Complex Network Dynamics: A Preliminary Study....Pages 637-646
Partner Matching Applications of Social Networks....Pages 647-656
YASCA: An Ensemble-Based Approach for Community Detection in Complex Networks....Pages 657-666
Mining the Key Structure of the Information Diffusion Network....Pages 667-675
Handling Big Data of Online Social Networks on a Small Machine....Pages 676-685
Erratum: A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem....Pages E1-E1
Erratum: Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties....Pages E2-E2
Back Matter....Pages -