Accepted Papers

003: Bandwidth of Convex Bipartite Graphs and Related Graph Classes
Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno

004: Tight Bounds on Local Search to Approximate The Maximum Satisfiability Problems
Daming Zhu, Shaohan Ma

007: Proper n-Cell Polycubes in n-3 Dimensions
Andrei Asinowski, Gill Barequet, Ronnie Barequet, and Günter Rote

011: Approximately Uniform Online Checkpointing
Lauri Ahlroth, Olli Pottonen, and André Schumacher

014: Making Abstraction Refinement Efficient in Model Checking
Cong Tian and Zhenhua Duan

017: (1+ε)-Competitive Algorithm for Online OVSF Code Assignment with Resource Augmentation
Yuichi Asahiro, Kenta Kanmera, Eiji Miyano

019: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
Minghui Jiang and Yong Zhang

020: Unavoidable Regularities in Long Words with Bounded Number of Symbol Occurrences
Juha Kortelainen, Tuomas Kortelainen, and Ari Vesanen

022: The Density Maximization Problem in Graphs
Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, Dorothea Wagner

026: The Topology Aware File Distribution Problem
Shawn T. O'Neil, Amitabh Chaudhary, Danny Z. Chen, and Haitao Wang

027: Largest Area Convex Hull of Axis-aligned Squares
Ovidiu Daescu, Wenqi Ju, Jun Luo, and Binhai Zhu

028: Derandomizing HSSW Algorithm for 3-SAT
Kazuhisa Makino, Suguru Tamaki, and Masaki Yamamoto

031: On the Right-seed Array of a String
Michalis Christou, Maxime Crochemore, Ondrej Guth, Costas S.
Iliopoulos, Solon P. Pissis

032: Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems
Tomoyuki Yamakami

035: Computing the Girth of a Planar Graph in Linear Time
Hsien-Chih Chang, and Hsueh-I Lu

040: Property Testing for Cyclic Groups and Beyond
Francois Le Gall and Yuichi Yoshida

042: Compressed Directed Acyclic Word Graph with application in Local Alignment
Do Huy Hoang and Sung Wing Kin

044: Algorithms for Partition of Some Class of Graphs under Compaction
Narayan Vikas

045: Canonizing Hypergraphs under Abelian Group Action
V. Arvind and Johannes Köbler

047: Summing Symbols in Mutual Recurrences
Berkeley R. Churchill and Edmund A. Lamagna

048: A New Conditionally Anonymous Ring Signature
Shengke Zeng and Shaoquan Jiang

049: Exact Parameterized Multilinear Monomial Counting via k-layers Subset Convolution and k-Disjoint Sum
Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, and Francis C.M. Lau

054: Dominating Set Counting in Graph Classes
Shuji Kijima, Yoshio Okamoto, and Takeaki Uno

056: An Integer Programming Approach for the Rural Postman Problem with Time Dependent Travel Times
Guozhen Tan and Jinghao Sun

066: Oblivious Transfer and n-Variate Linear Function Evaluation
Yeow Meng Chee, Huaxiong Wang, and Liang Feng Zhang

067: Strong I/O Lower Bounds for Binomial and FFT Computation Graphs
Desh Ranjan, John Savage, and Mohammad Zubair

068: Characterizations of Locally Testable Linear- and Affine-invariant Families
Angsheng Li, Yicheng Pan

070: Optimal Online Algorithms on Two Hierarchical Machines with Resource Augmentation
Yiwei Jiang and An Zhang

074: A New Variation of Hat Guessing Games
Tengyu Ma, Xiaoming Sun, and Huacheng Yu

076: A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Binh-Minh Bui-Xuan, Pinar Heggernes, Ross McConnell, Daniel Meister, and Andrzej Proskurowski

077: On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou

080: Matching and P_2-Packing: Weighted Versions
Qilong Feng, Jianxin Wang, Jianer Chen

081: Linear Time Algorithms for the Basis of Abelian Groups
Gregory Karagiorgos and Dimitrios Poulakis

082: FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time
Malte Brinkmeyer, Thasso Griebel, and Sebastian Böcker

089: Computing Majority with Triple Queries
Gianluca De Marco, Evangelos Kranakis, and Gabor Wiener

090: On Parameterized Independent Feedback Vertex Set
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh

091: On Totally Unimodularity of Edge-Edge Adjacency Matrices
Yusuke Matsumoto, Naoyuki Kamiyama, and Keiko Imai

093: Cograph Editing: Complexity and Parameterized Algorithms
Yunlong Liu, Jianxin Wang, Jiong Guo, and Jianer Chen

094: Task Ordering and Memory Management Problem for Degree of Parallelism Estimation
Sergiu Carpov, Jacques Carlier, Dritan Nace, and Renaud Sirdey

097: Improved Algorithms for the Point-Set Embeddability problem for Plane 3-Trees
Tanaeem M Moosa and M. Sohel Rahman

098: Scheduling Jobs on Heterogeneous Platforms
Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram

102: ReachFewL = ReachUL
Brady Garvin, Derrick Stolee, Raghunath Tewari, and N. V. Vinodchandran

103: Unconstrained and Constrained Fault-Tolerant Resource Allocation Problems
Kewen Liao and Hong Shen

106: Exploiting the Robustness on Power-Law Networks
Yilin Shen, Nam P. Nguyen, My T. Thai

107: A Kolmogorov Complexity Proof of the Lovász Local Lemma
Jochen Messner andThomas Thierauf

108: Unions of Disjoint NP-complete Sets
Christian Glaßer, John Hitchcocky, A. Pavan, and Stephen Travers

113: Flipping Triangles and Rectangles
Minghui Jiang

114: Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
Jin-Yi Cai and Michael Kowalczyk

115: Self-Assembling Rulers for Approximating Generalized Sierpinski Carpets
Steven M. Kautz and Brad Shutters

116: Quantum Algorithm for the Boolean Hidden Shift Problem
Dmitry Gavinsky, Martin Roetteler, and Jérémie Roland

117: Finding Paths with Minimum Shared Edges
Masoud T. Omran,  Jörg-Rüdiger Sack, and Hamid Zarrabi-Zadeh

128: Optimal Strategies for the One-Round Discrete Voronoi Game on a Line
Aritra Banik, Bhaswar B. Bhattacharya, and Sandip Das

131: Combinatorial Group Testing for Corruption Localizing Hashing
Annalisa De Bonis and Giovanni Di Crescenzo

132: Online Pricing for Identical Items
Yong Zhang, Francis Y.L. Chin, and Hing-Fung Ting

In COCOON 2011, we have totally 54 accepted papers, selected from 136 submissions.