CTW 2009: Paris, France

Traveling Salesman Problem

• Changxing Dong, Christian Ernst, Gerold Jäger, Dirk Richter, Paul Molitor:
  Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones. 3-6
  
• Marco Casazza, Alberto Ceselli, Marc Nunkesser:
  Efficient Algorithms for the Double Traveling Salesman Problem with Multiple Stacks. 7-10
  
• Maurizio Bruglieri, Alberto Colorni, Alessandro Lué:
  The Parking Warden Tour Problem. 11-15
  

Graph Theory I

• Ignasi Sau, Dimitrios M. Thilikos:
  On Self-Duality of Branchwidth in Graphs of Bounded Genus. 19-22
  
• Stavros D. Nikolopoulos, Charis Papadopoulos:
  A Simple Linear-Time Recognition Algorithm for Weakly Quasi-Threshold Graphs. 23-27
  
• Harald Gropp:
  From Sainte-Laguü to Claude Berge - French Graph Theory in the Twentieth Century. 28-32
  

Combinatorial Optimization

• Jens Maßberg, Tim Nieberg:
  Colored Independent Sets. 35-39
  
• Vadim V. Lozin:
  A Note on the Parameterized Complexity of the Maximum Independent Set Problem. 40-43
  
• Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy:
  On Multi-Agent Knapsack Problems. 44-47
  
• L. Simonetti, Yuri Frota, Cid C. de Souza:
  An Exact Method for the Minimum Caterpillar Spanning Problem. 48-51
  

Coloring I

• Raphael Machado, Celina M. Herrera de Figueiredo:
  NP-Completeness of Determining the Total Chromatic Number of Graphs that do not Contain a Cycle with a Unique Chord. 55-59
  
• Ross J. Kang, Tobias Müller:
  Acyclic and Frugal Colourings of Graphs. 60-63
  
• Petros A. Petrosyan, H. E. Sargsyan:
  On Resistance of Graphs. 64-67
  
• Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Vasileios Syrgkanis:
  Colored Resource Allocation Games. 68-72
  

Cutting and Packing

• Claudio Arbib, Fabrizio Marinelli, Carlo M. Scoppola:
  A Lower Bound for the Cutting Stock Problem with a Limited Number of Open Stacks. 75-78
  
• Henning Fernau, Daniel Raible:
  Packing Paths: Recycling Saves Time. 79-83
  
• Jens Maßberg, Jan Schneider:
  Rectangle Packing with Additional Restrictions. 84-86
  

Paths

• Fabio Luiz Usberti, Paulo Morelato Franca, André Luiz Morelato Franca:
  The Open Capacitated Arc Routing Problem. 89-92
  
• Mirko Maischberger:
  Optimising Node Coordinates for the Shortest Path Problem. 93-96
  
• Ramesh Bhandari:
  The Sliding Shortest Path Algorithms. 97-101
  

Quadratic Programming

• Walid Ben-Ameur, José Neto:
  A Polynomial-Time Recursive Algorithm for some Unconstrained Quadratic Optimization Problems. 105-108
  
• Ingmar Schüle, Hendrik Ewe, Karl-Heinz Küfer:
  Finding Tight RLT Formulations for Quadratic Semi-Assignment Problems. 109-112
  

Trees

• A. Abouelaoualim, V. Borozan, Yannis Manoussakis, Carlos A. J. Martinhon, R. Muthu, Rachid Saad:
  Colored Trees in Edge-Colored Graphs. 115-119
  
• Kathie Cameron, Joanna Fawcett:
  Intermediate Trees. 120-121
  

Plenary Session I

• Andrea Lodi, Ted K. Ralphs:
  Bilevel Programming and Maximally Violated Valid Inequalities. 125-134
  

Integer Programming

• Rüdiger Schultz:
  Decomposition Methods for Stochastic Integer Programs with Dominance Constraints. 137-139
  
• Stefanie Kosuch, Abdel Lisser:
  On a Two-Stage Stochastic Knapsack Problem with Probabilistic Constraint. 140-143
  
• Gérard Cornuéjols, Leo Liberti, Giacomo Nannicini:
  Improved Strategies for Branching on General Disjunctions. 144-145
  

Graph Theory II

• Gyula Y. Katona, Illés Horváth:
  Extremal Stable Graphs. 149-152
  
• Valeria A. Leoni, Maria Patricia Dobson, Graciela L. Nasini:
  Recognizing Edge-Perfect Graphs: some Polynomial Instances. 153-156
  
• Maria Aguieras A. de Freitas, Nair Maria Maia de Abreu, Renata R. Del-Vecchio:
  Some Infinite Families of Q-Integral Graphs. 157-160
  

Applications

• Alberto Ceselli, Roberto Cordone, Marco Cremonini:
  Balanced Clustering for Efficient Detection of Scientific Plagiarism. 163-170
  
• Valentina Cacchiani, Alberto Caprara, Matteo Fischetti:
  Robustness in Train Timetabling. 171-174
  
• Fabio Roda, Leo Liberti, Franco Raimondi:
  Combinatorial Optimization Based Recommender Systems. 175-179
  
• Roberto Cordone, Federico Ficarelli, Giovanni Righini:
  Bounds and Solutions for Strategic, Tactical and Operational Ambulance Location. 180-183
  

Coloring II

• Edna A. Hoshino, Yuri Frota, Cid C. de Souza:
  A Branch-and-Price Approach for the Partition Coloring Problem. 187-190
  
• María Soto, André Rossi, Marc Sevaux:
  Two Upper Bounds on the Chromatic Number. 191-194
  
• Flavia Bonomo, Guillermo Durán, Javier Marenco, Mario Valencia-Pabon:
  Minimum Sum Set Coloring on some Subclasses of Block Graphs. 195-198
  
• Andrew Lyons:
  Acyclic and Star Colorings of Joins of Graphs and an Algorithm for Cographs. 199-202
  

Exact Algorithms

• Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Daniel Raible:
  Exact Exponential-Time Algorithms for Finding Bicliques in a Graph. 205-209
  
• Lucio Bianco, Massimiliano Caramia:
  An Exact Algorithm to Minimize the Makespan in Project Scheduling with Scarce Resources and Feeding Precedence Relations. 210-214
  
• Rita Macedo, Cláudio Alves, José M. Valério de Carvalho:
  Exact Algorithms for Vehicle Routing Problems with Different Service Constraints. 215-218
  

Networks I

• Dmitrii Lozovanu, Stefan Pickl:
  Algorithmic Solutions of Discrete Control Problems on Stochastic Networks. 221-224
  
• Lucile Belgacem, Irène Charon, Olivier Hudry:
  Routing and Wavelength Assignment in Optical Networks by Independent Sets in Conflict Graphs. 225-228
  
• André Luiz Pires Guedes, Lilian Markenzon, L. Faria:
  Recognition of Reducible Flow Hypergraphs. 229-232
  

Complexity

• Andrea Scozzari, Fabio Tardella:
  On the Complexity of Graph-Based Bounds for the Probability Bounding Problem. 235-238
  
• Birgit Engels, Sven Oliver Krumke, Rainer Schrader, Christiane Zeck:
  Integer Flow with Multipliers: The Special Case of Multipliers 1 and 2. 239-243
  

Polyhedra

• Rüdiger Stephan:
  Classification of 0/1-Facets of the Hop Constrained Path Polytope Defined on an Acyclic Digraph. 247-250
  
• Anna Galluccio, Claudio Gentile, M. Macina, Paolo Ventura:
  The k-Gear Composition and the Stable Set Polytope. 251-254
  

Plenary Session II

• Michel Habib:
  Diameter and Center Computations in Networks. 257-258
  

Polynomial-time Algorithms

• Manuel Bodirsky, Gustav Nordh, Timo von Oertzen:
  Integer Programming with 2-Variable Equations and 1-Variable Inequalities. 261-264
  
• Dirk Müller:
  Faster Min-Max Resource Sharing and Applications. 265-268
  
• Andrea Bettinelli, Leo Liberti, Franco Raimondi, David Savourey:
  The Anonymous Subgraph Problem. 269-274
  

Graph Theory III

• Rafael Ayala, Desamparados Fernández-Ternero, J. A. Vilches:
  The Number of Excellent Discrete Morse Functions on Graphs. 277-280
  
• Flavia Bonomo, Guillermo Durán, Luciano N. Grippo, Martín Darío Safe:
  Partial Characterizations of Circle Graphs. 281-284
  
• Takeya Shigezumi, Yushi Uno, Osamu Watanabe:
  A Replacement Model for a Scale-Free Property of Cliques. 285-289
  

Graph Theory IV

• Andreas Darmann, Ulrich Pferschy, Joachim Schauer, Gerhard J. Woeginger:
  Combinatorial Optimization Problems with Conflict Graphs. 293-296
  
• Jose Maria Sigarreta, Ismael Gonález Yero, Sergio Bermudo, Juan Alberto Rodríguez-Velazquez:
  On the Decomposition of Graphs into Offensive k-Alliances. 297-300
  
• Michael Brinkmeier:
  Increasing the Edge Connectivity by One in O(lambda_G n^2 log* n) Expected Time. 301-304
  
• Vassilis Giakoumakis, Cheikh Brahim Ooud El Mounir:
  Enumerating all Finite Sets of Minimal Prime Extensions of Graphs. 305-309
  

Networks II

• Cédric Bentz:
  On Planar and Directed Multicuts with few Source-Sink Pairs. 313-316
  
• Fabio Luiz Usberti, José Federico Vizcaino González, Christiano Lyra Filho, Celso Cavellucci:
  Maintenance Resources Allocation on Power Distribution Networks with a Multi-Objective Framework. 317-320
  
• Enrico Grande, Pitu B. Mirchandani, Andrea Pacifici:
  Column Generation for the Multicommodity Min-cost Flow Over Time Problem. 321-324
  
• Fabien Tarissan, Camilo La Rota:
  Inferring Update Sequences in Boolean Gene Regulatory Networks. 325-329
  

Bioinformatics

• Gunnar Brinkmann, Nicolas Van Cleemput:
  NANOCONES - A Classification Result in Chemistry. 333-336
  
• Antonio Mucherino, Carlile Lavor, Nelson Maculan:
  The Molecular Distance Geometry Problem Applied to Protein Conformations. 337-340
  
• Guillaume Collet, Rumen Andonov, Nicola Yanev, Jean-François Gibrat:
  Protein Threading. 341-344
  

Clustering

• J. Correa, Nicole Megow, R. Raman, Karol Suchan:
  Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs. 347-350
  
• F. Liers, G. Pardella:
  A Simple MAX-CUT Algorithm for Planar Graphs. 351-354
  
• Edoardo Amaldi, Stefano Coniglio, Kanika Dhyani:
  k-Hyperplane Clustering Problem: Column Generation and a Metaheuristic. 355-358
  

Games

• Ulrich Faigle, Jan Voss:
  A System-Theoretic Model for Cooperation and Allocation Mechanisms. 361-364
  

Matrices

• Le Anh Vinh:
  Distribution of Permanent of Matrices with Restricted Entries over Finite Fields. 367-370
  

Plenary Session III

• Jon Lee:
  On the Boundary of Tractability for Nonlinear Discrete Optimization. 373-383