
Accepted Papers
The following is the list of papers that have been accepted for
COCOA 2008. The list of papers is given in arbritrary order.
 A Parameterized Perspective on Packing Paths of Length Two
Henning Fernau and Daniel Raible

New Algorithms for kcenter and Extensions
Rene Brandenberg and Lucia Roth

Separating Sublinear Time Computations by Approximate Diameter
Bin Fu and Zhiyu Zhao

Turan Graphs, Stability Number, and Fibonacci Index
Véronique Bruyère and Hadrien Mélot.

Vertexuncertainty in Graphproblems
Cécile Murat and Vangelis Paschos.

Flows with Unit Path Capacities and Related Packing and Covering Problems
Maren Martens and Martin Skutella

Strong Formulations for 2NodeConnected Steiner Network Problems
Markus Chimani, Maria Kandyba, Ivana Ljubic and Petra Mutzel

Enumerating Isolated Cliques in Synthetic and Financial Networks
Falk Hüffner, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier

Covering Arrays Avoiding Forbidden Edges (CAFE)
Peter Danziger, Eric Mendlesohn, Lucia Moura and Brett Stevens

Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
Shai Gutner

Protean Graphs With a Variety of Ranking Schemes
Pawel Pralat

Optimal Movement of Mobile Sensors for Barrier Coverage
Binay Bhattacharya, Mike Burmester, Yuzhuang Hu, Evangelos Kranakis, Qiaosheng Shi and Andreas Wiese

Simplicial Powers of Graphs
Andreas Brandstadt and Bang van Le

An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem
Zhipeng Cai, ZhiZhong Chen, Guohui Lin and Lusheng Wang

On k versus (k+1)Leaf Powers
Andreas Brandstadt and Peter Wagner

Going Weighted: Parameterized Algorithms for Cluster Editing
Sebastian Boecker, Sebastian Briesemeister, Quang Bao Anh Bui and Anke Truss

Two Constant Approximation Algorithms for NodeWeighted Steiner Tree in Unit Disk Graphs
Feng Zou, Xianyue Li, Donghyun Kim and Weili Wu

Computational Study on Dominating Set Problem of Planar Graphs
Marjan Marzban, Qianping Gu and Xiaohua Jia

The Robot Cleans Up
MargaretEllen Messinger and R.J. Nowakowski

On the Stable Set Polytope of ClawFree Graphs
Anna Galluccio, Claudio Gentile and Paolo Ventura

Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
Nadja Betzler and Johannes Uhlmann

Parameterized Graph Editing with Chosen Vertex Degrees
Luke Mathieson and Stefan Szeider

A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs that are Join of Regular Graphs
Caterina De Simone and Anna Galluccio

Multiple Hypernode Hitting Sets and Smallest Twocores with Targets
Peter Damaschke

FixedParameter Tractability of Anonymizing Data by Suppressing Entries
Rhonda Chaytor, Patricia Evans and Todd Wareham

An Improved PrimalDual Approximation Algorithm for the Connected Facility Location Problem
Hyunwoo Jung, Mohammad Khairul Hasan and KyungYong Chwa

Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
Zhao Zhang, Xiaofeng Gao and Weili Wu

Magic Labelings on Cycles and Wheels
Andrew Baker and Joe Sawada

Clustered SplitsNetworks
Lichen Bao and Sergey Bereg

Minimum Cost Homomorphism Dichotomy for Locally InSemicomplete Digraphs
Mehdi Karimi, Arvind Gupta, Arash Rafiey and Eun Jung Kim

Fast Computation of PointtoPoint Paths on Timedependent Road Networks
Giacomo Nannicini, Philippe Baptiste, Daniel Krob and Leo Liberti

Parameterized Algorithms for Generalized Domination
Venkatesh Raman, Saket Saurabh and Sriganesh Srihari

Delay Management Problem: Complexity Results and Robust Algorithms
Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni and Alfredo Navarra

A RiskReward Competitive Analysis for the Recoverable Canadian Traveler Problem
Bing Su, Yinfeng Xu, Peng Xiao and Lei Tian

Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization
Karine Deschinkel and SidAhmedAli Touati

Minimizing Total Completion Time in TwoMachine Flow Shops With Exact Delay
Hairong Zhao, Yumei Huo and Haibing Li

Stochastic Online Scheduling Revisited
Andreas S. Schulz

The Clique Corona Operation and Greedoids
Vadim Levit and Eugen Mandrescu

On the Surface Area of the (n, k)Star Graph
Zhi Zhang Shen, Ke Qiu and Eddie Cheng

Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
Gerold Jaeger and Paul Molitor

Automatic Generation of Symmetrybreaking Constraints
Leo Liberti

Algorithms and Implementation for Interconnection Graph Problem
Hongbing Fan, Christian Hundt, YuLiang Wu and Jason Ernst

Ant Colony Optimization Metaheuristic For Traffic Grooming in WDM Networks
Xiangyong Li, Yash Aneja and Fazle Baki

On Recovering Syntenic Blocks from Comparative Maps
Zhixiang Chen, Bin Fu, Minghui Jiang, and Binhai Zhu


