Computing and Combinatorics

1. Front Matter

   PDF

2. Derandomizing HSSW Algorithm for 3-SAT

   • Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

   Pages 1-12

3. Dominating Set Counting in Graph Classes

   • Shuji Kijima, Yoshio Okamoto, Takeaki Uno

   Pages 13-24

4. The Density Maximization Problem in Graphs

   • Mong-Jen Kao, Bastian Katz, Marcus Krug, D. T. Lee, Ignaz Rutter, Dorothea Wagner

   Pages 25-36

5. FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time

   • Malte Brinkmeyer, Thasso Griebel, Sebastian Böcker

   Pages 37-48

6. Tight Bounds on Local Search to Approximate the Maximum Satisfiability Problems

   • Daming Zhu, Shaohan Ma, Pingping Zhang

   Pages 49-61

7. Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy

   • Minghui Jiang, Yong Zhang

   Pages 62-73

8. Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum

   • Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis C. M. Lau

   Pages 74-85

9. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms

   • Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

   Pages 86-97

10. On Parameterized Independent Feedback Vertex Set

    • Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh

    Pages 98-109

11. Cograph Editing: Complexity and Parameterized Algorithms

    • Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer Chen

    Pages 110-121

12. Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems

    • Tomoyuki Yamakami

    Pages 122-133

13. Strong I/O Lower Bounds for Binomial and FFT Computation Graphs

    • Desh Ranjan, John Savage, Mohammad Zubair

    Pages 134-145

14. Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities

    • Jin-Yi Cai, Michael Kowalczyk

    Pages 146-157

15. Quantum Algorithm for the Boolean Hidden Shift Problem

    • Dmitry Gavinsky, Martin Roetteler, Jérémie Roland

    Pages 158-167

16. A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

    • Jochen Messner, Thomas Thierauf

    Pages 168-179

17. Proper n-Cell Polycubes in n − 3 Dimensions

    • Andrei Asinowski, Gill Barequet, Ronnie Barequet, Günter Rote

    Pages 180-191

18. Largest Area Convex Hull of Axis-Aligned Squares Based on Imprecise Data

    • Ovidiu Daescu, Wenqi Ju, Jun Luo, Binhai Zhu

    Pages 192-203

19. Improved Algorithms for the Point-Set Embeddability Problem for Plane 3-Trees

    • Tanaeem M. Moosa, M. Sohel Rahman

    Pages 204-212

20. Optimal Strategies for the One-Round Discrete Voronoi Game on a Line

    • Aritra Banik, Bhaswar B. Bhattacharya, Sandip Das

    Pages 213-224

This book constitutes the refereed proceedings of the 17th Annual International Conference on Computing and Combinatorics, held in Dallas, TX, USA, in August 2011. The 54 revised full papers presented were carefully reviewed and selected from 136 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; parallel and distributed computing.

• algorithmic geometry
• algorithmic learning
• combinatorial optimization
• discrete mathematics
• graph algorithms
• graph computation
• network computation
• algorithm analysis and problem complexity

• Department of Computer Science, University of Texas-Pan American, Edinburg, USA

  Bin Fu

• Department of Computer Science, University of Texas at Dallas, Richardson, USA

  Ding-Zhu Du

Policies and ethics