Combinatorial Algorithms

1. Front Matter

   PDF

2. Bounds on Quasi-Completeness

   • Malay Bhattacharyya, Sanghamitra Bandyopadhyay

   Pages 1-5

3. Infinite Random Geometric Graphs from the Hexagonal Metric

   • Anthony Bonato, Jeannette Janssen

   Pages 6-19

4. Saving on Phases: Parameterized Approximation for Total Vertex Cover

   • Henning Fernau

   Pages 20-31

5. On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths

   • Florent Foucaud, Matjaž Kovše

   Pages 32-45

6. Disjoint Set Forest Digraph Representation for an Efficient Dominator Tree Construction

   • Wojciech Fraczak, Andrew Miller

   Pages 46-59

7. On Some Properties of Doughnut Graphs

   • Md. Rezaul Karim, Md. Jawaherul Alam, Md. Saidur Rahman

   Pages 60-64

8. On the Steiner Radial Number of Graphs

   • K. M. Kathiresan, S. Arockiaraj, R. Gurusamy, K. Amutha

   Pages 65-72

9. Further Results on the Mycielskian of Graphs

   • T. Kavaskar

   Pages 73-75

10. Approaches and Mathematical Models for Robust Solutions to Optimization Problems with Stochastic Problem Data Instances

    • Niraj Ramesh Dayama, Ketki Kulkarni

    Pages 76-80

11. Faster Replacement Paths Algorithm for Undirected, Positive Integer Weighted Graphs with Small Diameter

    • Jay Mahadeokar, Sanjeev Saxena

    Pages 81-85

12. Acyclic Coloring with Few Division Vertices

    • Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, Sue Whitesides

    Pages 86-99

13. Degree Associated Edge Reconstruction Number

    • S. Monikandan, S. Sundar Raj

    Pages 100-109

14. Touring Polygons: An Approximation Algorithm

    • Amirhossein Mozafari, Alireza Zarei

    Pages 110-121

15. Super Connectivity of the Generalized Mycielskian of Graphs

    • S. Francis Raj

    Pages 122-124

16. A Graph Radio k-Coloring Algorithm

    • Laxman Saha, Pratima Panigrahi

    Pages 125-129

17. Maximum Order of a Planar Oclique Is 15

    • Sagnik Sen

    Pages 130-142

18. Sufficient Condition for {C ₄, C _2t } - Decomposition of K _2m,2n – An Improved Bound

    • Shanmugasundaram Jeevadoss, Appu Muthusamy

    Pages 143-147

19. Incomparability Graphs of Lattices II

    • Meenakshi Wasadikar, Pradnya Survase

    Pages 148-161

20. On Antimagic Labeling of Odd Regular Graphs

    • Tao-Ming Wang, Guang-Hui Zhang

    Pages 162-168

This book constitutes the thoroughly referred post-workshop proceedings of the 23rd International Workshop on Combinatorial Algorithms, IWOCA 2012, held in Krishnankoil, Tamil Nadu, India, in July 2012. The 32 revised full papers presented were carefully reviewed and selected from a total of 88 submissions. The papers are organized in topical sections in algorithms and data Structures, applications (including Bioinformatics, Networking, etc.), combinatorics of words and strings, combinatorial optimization, combinatorial enumeration, decompositions and combinatorial designs, complexity theory (structural and computational), computational biology and graph theory and combinatorics submissions.

• approximation algorithm
• computational geometry
• grid drawing
• planar graph
• structural matching
• algorithm analysis and problem complexity
• data structures

• Kalasalingam University, Krishanakoil, India

  S. Arumugam

• Algorithms Research Group, Department of Computing & Software, McMaster University, Hamilton, Canada

  W. F. Smyth

Policies and ethics