Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings

✍ Scribed by Jing (Selena) He, Shouling Ji, Yi Pan (auth.), Guohui Lin (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2012
• Tongue: English
• Leaves: 407
• Series: Lecture Notes in Computer Science 7402
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 6th International Conference, COCOA 2012, held in Banff, Alberta, Canada, in August 2012. The 33 revised papers including one invited talk and one keynote talk were carefully reviewed and selected from 57 submissions. The papers are focused to theoretical results and also on recent works on experimental and applied research of general algorithmic interest.

✦ Table of Contents

Front Matter....Pages -
Load-Balanced Virtual Backbone Construction for Wireless Sensor Networks....Pages 1-12
Maximum Matching in Multi-Interface Networks....Pages 13-24
Stretch Factor in Wireless Sensor Networks with Directional Antennae....Pages 25-36
On the Minimum Diameter Cost-Constrained Steiner Tree Problem....Pages 37-48
The Edge-Centered Surface Area of the Arrangement Graph....Pages 49-60
On Zero Forcing Number of Permutation Graphs....Pages 61-72
Complexity Results for the Empire Problem in Collection of Stars....Pages 73-82
Hamiltonian Paths and Cycles in Planar Graphs....Pages 83-94
Feedback Vertex Sets on Tree Convex Bipartite Graphs....Pages 95-102
Crossing Angles of Geometric Graphs....Pages 103-114
Multicut on Graphs of Bounded Clique-Width....Pages 115-126
Radiation Hybrid Map Construction Problem Parameterized....Pages 127-137
On the Central Path Problem....Pages 138-150
On the Generalized Multiway Cut in Trees Problem....Pages 151-162
Algorithms for Forest Local Similarity....Pages 163-175
Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method....Pages 176-187
An Improved Approximation Algorithm for the Bandpass-2 Problem....Pages 188-199
The b -Matching Problem in Hypergraphs: Hardness and Approximability....Pages 200-211
Resource Scheduling with Supply Constraint and Linear Cost....Pages 212-222
On Certain Geometric Properties of the Yao-Yao Graphs....Pages 223-233
Distance- d Independent Set Problems for Bipartite and Chordal Graphs....Pages 234-244
Domatic Partition on Several Classes of Graphs....Pages 245-256
Online Bottleneck Matching....Pages 257-268
Streaming with Minimum Space: An Algorithm for Covering by Two Congruent Balls....Pages 269-280
Online Joint Pricing and Booking Policies in Airline Revenue Management....Pages 281-290
Minimizing Total Weighted Completion Time with Unexpected Machine Unavailability....Pages 291-300
Characterizing Mechanisms in Obnoxious Facility Game....Pages 301-311
Efficiency of Dual Equilibria in Selfish Task Allocation to Selfish Machines....Pages 312-323
Fast-Mixed Searching on Graphs....Pages 324-335
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems....Pages 336-347
Dynamic Programming for a Biobjective Search Problem in a Line....Pages 348-359
Characterizing Graphs of Small Carving-Width....Pages 360-370
Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming....Pages 371-383
Measuring Structural Similarities of Graphs in Linear Time....Pages 384-395
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Algorithms; Computer Communication Networks