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 nCell Polycubes in n3 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 MultipleInterval 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
MongJen 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 Axisaligned Squares
Ovidiu Daescu, Wenqi Ju, Jun Luo, and Binhai Zhu
028: Derandomizing HSSW Algorithm for 3SAT
Kazuhisa Makino, Suguru Tamaki, and Masaki Yamamoto
031: On the Rightseed Array of a String
Michalis Christou, Maxime Crochemore, Ondrej Guth, Costas S.
Iliopoulos, Solon P. Pissis
032: Approximation Complexity of ComplexWeighted DegreeTwo Counting Constraint Satisfaction Problems Tomoyuki Yamakami
035: Computing the Girth of a Planar Graph in Linear Time
HsienChih Chang, and HsuehI 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 klayers Subset Convolution and kDisjoint Sum
Dongxiao Yu, Yuexuan Wang, QiangSheng 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 nVariate 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 Affineinvariant 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
BinhMinh BuiXuan, 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_2Packing: 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 EdgeEdge 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 PointSet Embeddability problem for Plane 3Trees
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 FaultTolerant Resource Allocation Problems
Kewen Liao and Hong Shen
106: Exploiting the Robustness on PowerLaw 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 NPcomplete 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
JinYi Cai and Michael Kowalczyk
115: SelfAssembling 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örgRüdiger Sack, and Hamid ZarrabiZadeh
128: Optimal Strategies for the OneRound 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 HingFung Ting
In COCOON 2011, we have totally 54 accepted papers, selected from 136 submissions.
