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

Description

This book constitutes the refereed proceedings of the 18th Annual International Conference on Computing and Combinatorics, held in Sydney, Australia, in August 2012. The 50 revised full papers presented were carefully reviewed and selected from 121 submissions. Topics covered are algorithms and data structures; algorithmic game theory and online algorithms; automata, languages, logic, and computability; combinatorics related to algorithms and complexity; complexity theory; computational learning theory and knowledge discovery; cryptography, reliability and security, and database theory; computational biology and bioinformatics; computational algebra, geometry, and number theory; graph drawing and information visualization; graph theory, communication networks, and optimization. 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 -