

Contributed papers (extended abstracts)
More than 100 extended abstracts were submitted.
On average, each was reviewed by 3 different reviewers.
The accepted papers are listed below in the order they were
received.

Three classes of minimal circularimperfect graphs
Arnaud Pêcher,
Annegret K. Wagler,
Xuding Zhu

Upper bound on the noncolorability threshold of the 2+pCOL problem
Roberto Cruz

Searching for geodetic boundary vertex sets
J. Cáceres,
M. L. Puertas,
C. Hernando,
M. Mora,
I. M. Pelayo,
C. Seara

Building PQR trees in almostlinear time
Guilherme P. Telles,
João Meidanis

A multistart constructive heuristic for sequencing by hybridization using adaptive memory
Eraldo R. Fernandes,
Celso C. Ribeiro

(p,k)colorings in line graphs
Marc Demange,
Tinaz Ekim,
Dominique de Werra

On the local splitting theorem
Zoltán Szigeti

The combinatorial stages of chromatic scheduling polytopes
Javier Marenco,
Annegret Wagler

The Helly property on subhypergraphs
Mitre C. Dourado,
Fábio Protti,
Jayme L. Szwarcfiter

On the computational complexity of partial covers of Theta graphs
Jiří Fiala,
Jan Kratochvíl,
Attila Pór

Generating all the cubic graphs that have a 6cycle double cover
Rodrigo S. C. Leão,
Valmir C. Barbosa

Partial characterizations of cliqueperfect graphs
Flavia Bonomo,
Maria Chudnovsky,
Guillermo Durán

The nodeedge weighted 2edge connected subgraph problem: linear relaxation, facets and separation
Mourad Baïou,
José R. Correa

On bags and bugs
Pierre Hansen,
Dragan Stevanović

Between coloring and listcoloring: \mucoloring
Flavia Bonomo,
Mariano Cecowski

A Gray code for binary subtraction
Joe Sawada

An allsubstrings common subsequence algorithm
C. E. R. Alves,
E. N. Cáceres,
S. W. Song

Randomized mechanisms for limited supply multiitem auctions
Claudson F. Bornstein,
Eduardo Sany Laber,
Marcelo A. F. Más

Nonseparating cocircuits in matroids
Manoel Lemos,
T. R. B. Melo

On the Hadwiger number of hypercubes and its generalizations
L. Sunil Chandran,
Naveen Sivadasan

The distribution of the path edgecovering numbers for random trees
Alois Panholzer

Improved bounds on acyclic edge colouring
Rahul Muthu,
Narayanan N.,
C. R. Subramanian

Globally bounded local edge colourings of hypergraphs
Mathias Schacht,
Anusch Taraz

Search locally to arrange cyclically
Murali K. Ganapathy,
Sachin P. Lodha

Probe interval bigraphs
Gerard Jennhwa Chang,
Ton Kloks,
ShengLung Peng

On some applications of randomized memory
Vince Grolmusz

A general approach to L(h,k)label interconnection networks
Tiziana Calamoneri,
Saverio Caminiti,
Rossella Petreschi

Lehman's equation on nearideal clutters
G. Argiroffo,
S. Bianchi,
G. Nasini

Optimal flow distribution among multiple channels with unknown capacities
Richard Karp,
Till Nierhoff,
Till Tantau

Detecting flows congesting a target network link
D. Barth,
P. Berthomé,
M. Diallo

Computing the integrality gap of the asymmetric travelling salesman problem
Sylvia Boyd,
Paul ElliottMagwood

Advances in packing directed joins
Aaron M. Williams,
Bertrand Guenin

Degree constrained subgraphs
L. AddarioBerry,
K. Dalal,
B. A. Reed

Planar graph bipartization in linear time
Samuel Fiorini,
Nadia Hardy,
Bruce Reed,
Adrian Vetta

Faster algorithms for feedback vertex set
Venkatesh Raman,
Saket Saurabh,
C. R. Subramanian

A forbidden subgraph characterization of path graphs
Silvia B. Tondato,
Marisa Gutierrez,
Jayme L. Szwarcfiter

Non loop graphs with induced cycles
Liliana Alcón,
Márcia R. Cerioli,
Celina M. H. de Figueiredo,
Marisa Gutierrez,
João Meidanis

Fractionally total colouring G(n,p)
Conor Meagher,
Bruce Reed

Forbidden subgraph characterization of split graphs that are UEH
M. R. Cerioli,
P. Petito

Two and threedimensional parametric packing
F. K. Miyazawa,
Y. Wakabayashi

Large kindependent sets of random regular graphs
Mihalis Beis,
William Duckworth,
Michele Zito

A onedimensional bin packing problem with shelf divisions
E. C. Xavier,
F. K. Miyazawa

On the asymmetric representatives formulation for the vertex coloring problem
Manoel Campêlo,
Victor Campos,
Ricardo Corrêa

Local cutpoints and iterated clique graphs
M. E. FríasArmenta,
F. Larrión,
V. NeumannLara,
M. A. Pizaña

On hereditary Helly selfclique graphs
F. Larrión,
M. A. Pizaña

A new family of Kdivergent graphs
Martín Matamala,
José Zamora

Alignment with nonoverlapping inversions in O(n³ log n) time
Carlos E. R. Alves,
Alair Pereira do Lago,
Augusto F. Vellozo

A new refinement procedure for graph isomorphism algorithms
Mateus de Oliveira Oliveira,
Fabíola Greve

Two aspects of the pallet loading problem
Walter F. Mascarenhas

Stabilized branchandcutandprice for the generalized assignment problem
Alexandre Pigatti,
Marcus Poggi de Aragão,
Eduardo Uchoa

The 3colored Ramsey number of odd cycles
Yoshiharu Kohayakawa,
Miklós Simonovits,
Jozef Skokan

Algorithms for the degreeconstrained minimum spanning tree problem
Alexandre Salles da Cunha,
Abilio Lucena

Perfect subgraph/supergraph
Murilo V. G. da Silva,
André L. P. Guedes
