Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings

Front Matter....Pages -
A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree....Pages 1-12
A Simple D 2 -Sampling Based PTAS for k -Means and other Clustering Problems....Pages 13-24
Speed Scaling for Maximum Lateness....Pages 25-36
Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others?....Pages 37-48
Contiguous Minimum Single-Source-Multi-Sink Cuts in Weighted Planar Graphs....Pages 49-60
Online Knapsack Problem with Removal Cost....Pages 61-73
An Improved Exact Algorithm for TSP in Degree-4 Graphs....Pages 74-85
Dynamic Programming for H -minor-free Graphs....Pages 86-97
Restricted Max-Min Fair Allocations with Inclusion-Free Intervals....Pages 98-108
An Improved Algorithm for Packing T -Paths in Inner Eulerian Networks....Pages 109-120
Towards Optimal and Expressive Kernelization for d -Hitting Set....Pages 121-132
Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs....Pages 133-144
A Local Algorithm for Finding Dense Bipartite-Like Subgraphs....Pages 145-156
Algorithms for the Strong Chromatic Index of Halin Graphs, Distance-Hereditary Graphs and Maximal Outerplanar Graphs....Pages 157-168
On the Minimum Degree Hypergraph Problem with Subset Size Two and the Red-Blue Set Cover Problem with the Consecutive Ones Property....Pages 169-180
Rainbow Colouring of Split and Threshold Graphs....Pages 181-192
Approximating the Rainbow – Better Lower and Upper Bounds....Pages 193-203
Ramsey Numbers for Line Graphs and Perfect Graphs....Pages 204-215
Geodesic Order Types....Pages 216-227
Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number....Pages 228-239
Monotone Paths in Planar Convex Subdivisions....Pages 240-251
The Cost of Bounded Curvature....Pages 252-263
Optimally Solving a Transportation Problem Using Voronoi Diagrams....Pages 264-274
Unexplored Steiner Ratios in Geometric Networks....Pages 275-286
Geometric RAC Simultaneous Drawings of Graphs....Pages 287-298
Simultaneous Embeddings with Vertices Mapping to Pre-specified Points....Pages 299-310
Multilevel Drawings of Clustered Graphs....Pages 311-322
Outerplanar Graph Drawings with Few Slopes....Pages 323-334
Fáry’s Theorem for 1-Planar Graphs....Pages 335-346
Constant Time Enumeration of Bounded-Size Subtrees in Trees and Its Application....Pages 347-359
External Memory Soft Heap, and Hard Heap, a Meldable Priority Queue....Pages 360-371
Partially Specified Nearest Neighbor Search....Pages 372-383
Multi-pattern Matching with Bidirectional Indexes....Pages 384-395
Succinct Representations of Binary Trees for Range Minimum Queries....Pages 396-407
Lower Bounds against Weakly Uniform Circuits....Pages 408-419
On TC 0 Lower Bounds for the Permanent....Pages 420-432
Formula Complexity of Ternary Majorities....Pages 433-444
On the Kernelization Complexity of Problems on Graphs without Long Odd Cycles....Pages 445-457
The Complexity of Unary Subset Sum....Pages 458-469
On the Advice Complexity of Tournaments....Pages 470-481
A Remark on One-Wayness versus Pseudorandomness....Pages 482-494
Integral Mixed Unit Interval Graphs....Pages 495-506
Complementary Vertices and Adjacency Testing in Polytopes....Pages 507-518
Online Coloring of Bipartite Graphs with and without Advice....Pages 519-530
Deep Coalescence Reconciliation with Unrooted Gene Trees: Linear Time Algorithms....Pages 531-542
On the 2-Central Path Problem....Pages 543-555
Making Profit in a Prediction Market....Pages 556-567
Computing Shapley Value in Supermodular Coalitional Games....Pages 568-579
Equilibria of GSP for Range Auction....Pages 580-591
Stretch in Bottleneck Games....Pages 592-603
Back Matter....Pages -