Computing and Combinatorics

1. Front Matter

   PDF

2. A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree

   • Binay Bhattacharya, Tsunehiko Kameda

   Pages 1-12

3. A Simple D ²-Sampling Based PTAS for k-Means and other Clustering Problems

   • Ragesh Jaiswal, Amit Kumar, Sandeep Sen

   Pages 13-24

4. Speed Scaling for Maximum Lateness

   • Evripidis Bampis, Dimitrios Letsios, Ioannis Milis, Georgios Zois

   Pages 25-36

5. Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others?

   • Peter Floderus, Mirosław Kowaluk, Andrzej Lingas, Eva-Marta Lundell

   Pages 37-48

6. Contiguous Minimum Single-Source-Multi-Sink Cuts in Weighted Planar Graphs

   • Ivona Bezáková, Zachary Langley

   Pages 49-60

7. Online Knapsack Problem with Removal Cost

   • Xin Han, Yasushi Kawase, Kazuhisa Makino

   Pages 61-73

8. An Improved Exact Algorithm for TSP in Degree-4 Graphs

   • Mingyu Xiao, Hiroshi Nagamochi

   Pages 74-85

9. Dynamic Programming for H-minor-free Graphs

   • Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos

   Pages 86-97

10. Restricted Max-Min Fair Allocations with Inclusion-Free Intervals

    • Monaldo Mastrolilli, Georgios Stamoulis

    Pages 98-108

11. An Improved Algorithm for Packing T-Paths in Inner Eulerian Networks

    • Maxim A. Babenko, Kamil Salikhov, Stepan Artamonov

    Pages 109-120

12. Towards Optimal and Expressive Kernelization for d-Hitting Set

    • René van Bevern

    Pages 121-132

13. Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs

    • Jean-François Couturier, Pinar Heggernes, Pim van ’t Hof, Yngve Villanger

    Pages 133-144

14. A Local Algorithm for Finding Dense Bipartite-Like Subgraphs

    • Pan Peng

    Pages 145-156

15. Algorithms for the Strong Chromatic Index of Halin Graphs, Distance-Hereditary Graphs and Maximal Outerplanar Graphs

    • Ton Kloks, Sheung-Hung Poon, Chin-Ting Ung, Yue-Li Wang

    Pages 157-168

16. On the Minimum Degree Hypergraph Problem with Subset Size Two and the Red-Blue Set Cover Problem with the Consecutive Ones Property

    • Biing-Feng Wang, Chih-Hsuan Li

    Pages 169-180

17. Rainbow Colouring of Split and Threshold Graphs

    • L. Sunil Chandran, Deepak Rajendraprasad

    Pages 181-192

18. Approximating the Rainbow – Better Lower and Upper Bounds

    • Alexandru Popa

    Pages 193-203

19. Ramsey Numbers for Line Graphs and Perfect Graphs

    • Rémy Belmonte, Pinar Heggernes, Pim van ’t Hof, Reza Saei

    Pages 204-215

20. Geodesic Order Types

    • Oswin Aichholzer, Matias Korman, Alexander Pilz, Birgit Vogtenhuber

    Pages 216-227

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.

• approximation
• data structure
• one-way function
• pseudorandom generator
• traveling salesman problem
• algorithm analysis and problem complexity

• School of IT, University of Sydney, Sydney, Australia

  Joachim Gudmundsson, Julián Mestre, Taso Viglas

Policies and ethics