Computing and combinatorics: 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013: proceedings

Front Matter....Pages -
Recent Results for Online Makespan Minimization....Pages 1-3
Optimal Stopping Meets Combinatorial Optimization....Pages 4-4
New Bounds for the Balloon Popping Problem....Pages 5-16
On the Sequential Price of Anarchy of Isolation Games....Pages 17-28
Social Exchange Networks with Distant Bargaining....Pages 29-40
The 1/4-Core of the Uniform Bin Packing Game Is Nonempty....Pages 41-52
On the Advice Complexity of the Online L (2,1)-Coloring Problem on Paths and Cycles....Pages 53-64
On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets....Pages 65-76
A Fast Algorithm for Data Collection along a Fixed Track....Pages 77-88
Random Methods for Parameterized Problems....Pages 89-100
DVS Scheduling in a Line or a Star Network of Processors....Pages 101-113
Online Algorithms for Batch Machines Scheduling with Delivery Times....Pages 114-121
How to Schedule the Marketing of Products with Negative Externalities....Pages 122-133
From Preemptive to Non-preemptive Speed-Scaling Scheduling....Pages 134-146
Selection from Read-Only Memory with Limited Workspace....Pages 147-157
Deternimization of Büchi Automata as Partitioned Automata....Pages 158-168
On Linear-Size Pseudorandom Generators and Hardcore Functions....Pages 169-181
A Fast Algorithm Finding the Shortest Reset Words....Pages 182-196
The Discrete Voronoi Game in a Simple Polygon....Pages 197-207
Facets for Art Gallery Problems....Pages 208-220
Hitting and Piercing Rectangles Induced by a Point Set....Pages 221-232
Realistic Roofs over a Rectilinear Polygon Revisited....Pages 233-244
Parametric Power Supply Networks....Pages 245-256
Approximating the Minimum Independent Dominating Set in Perturbed Graphs....Pages 257-267
A Linear-Time Algorithm for the Minimum Degree Hypergraph Problem with the Consecutive Ones Property....Pages 268-279
On the Conjunctive Capacity of Graphs....Pages 280-291
Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty....Pages 292-303
An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems....Pages 304-315
Improved Local Search for Universal Facility Location....Pages 316-324
Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints....Pages 325-336
The k -Separator Problem....Pages 337-348
On the Treewidth of Dynamic Graphs....Pages 349-360
Square-Orthogonal Drawing with Few Bends per Edge....Pages 361-372
Covering Tree with Stars....Pages 373-384
A Polynomial Time Approximation Scheme for the Closest Shared Center Problem....Pages 385-396
An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies....Pages 397-408
An Efficient Algorithm for One-Sided Block Ordering Problem with Block-Interchange Distance....Pages 409-420
A Combinatorial Approach for Multiple RNA Interaction: Formulations, Approximations, and Heuristics....Pages 421-433
Maximum Balanced Subgraph Problem Parameterized above Lower Bound....Pages 434-445
A Toolbox for Provably Optimal Multistage Strict Group Testing Strategies....Pages 446-457
A Linear Edge Kernel for Two-Layer Crossing Minimization....Pages 458-468
A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product....Pages 469-480
Metrical Service Systems with Multiple Servers....Pages 481-492
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity....Pages 493-505
Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing and Square Packing....Pages 506-517
Improved Lower Bounds for the Online Bin Packing Problem with Cardinality Constraints....Pages 518-530
Parameterized Complexity of Flood-Filling Games on Trees....Pages 531-542
Parameterized Approximability of Maximizing the Spread of Influence in Networks....Pages 543-554
An Effective Branching Strategy for Some Parameterized Edge Modification Problems with Multiple Forbidden Induced Subgraphs....Pages 555-566
Parameterized Algorithms for Maximum Agreement Forest on Multiple Trees....Pages 567-578
Small H -Coloring Problems for Bounded Degree Digraphs....Pages 579-590
Bounded Model Checking for Propositional Projection Temporal Logic....Pages 591-602
Packing Cubes into a Cube Is NP-Hard in the Strong Sense....Pages 603-613
On the Complexity of Solving or Approximating Convex Recoloring Problems....Pages 614-625
2-connecting Outerplanar Graphs without Blowing Up the Pathwidth....Pages 626-637
How to Catch L 2 -Heavy-Hitters on Sliding Windows....Pages 638-650
Time/Memory/Data Tradeoffs for Variants of the RSA Problem....Pages 651-662
An Improved Algorithm for Extraction of Exact Boundaries and Boundaries Inclusion Relationship....Pages 663-671
Straight-Line Monotone Grid Drawings of Series-Parallel Graphs....Pages 672-679
Combination of Two-Machine Flow Shop Scheduling and Shortest Path Problems....Pages 680-687
The Program Download Problem: Complexity and Algorithms....Pages 688-696
Finding Theorems in NBG Set Theory by Automated Forward Deduction Based on Strong Relevant Logic....Pages 697-704
Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data....Pages 705-712
Sublinear Time Approximate Sum via Uniform Random Sampling....Pages 713-720
Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)....Pages 721-728
On the Minimum Caterpillar Problem in Digraphs....Pages 729-736
A New Model for Product Adoption over Social Networks....Pages 737-746
Generating Uncertain Networks Based on Historical Network Snapshots....Pages 747-758
A Short-Term Prediction Model of Topic Popularity on Microblogs....Pages 759-769
Social Network Path Analysis Based on HBase....Pages 770-779
Community Expansion Model Based on Charged System Theory....Pages 780-790
Centrality and Spectral Radius in Dynamic Communication Networks....Pages 791-800
Finding Network Communities Using Random Walkers with Improved Accuracy....Pages 801-810
Homophilies and Communities Detection among a Subset of Blogfa Persian Weblogs: Computer and Internet Category....Pages 811-820
Neighborhood-Based Dynamic Community Detection with Graph Transform for 0-1 Observed Networks....Pages 821-830
Effects of Inoculation Based on Structural Centrality on Rumor Dynamics in Social Networks....Pages 831-840
A Dominating Set Based Approach to Identify Effective Leader Group of Social Network....Pages 841-848
Using Network Sciences to Evaluate the Brazilian Airline Network....Pages 849-858
Back Matter....Pages -