216 
Equitable total coloring of cubic graphs is NPcomplete 


Simone Dantas, Celina M. H. De Figueiredo, Giuseppe Mazzuoccolo, Myriam Preissman, Vinicius F. Dos Santos, Diana Sasaki
A total coloring is equitable if the number of elements colored with each color differs by Keywords: total coloring, equitable total coloring, cubic graphs


215 
Integer roundup property for the chromatic number of some hperfect graphs 


Yohann Benchetrit
A graph is hperfect if its stable set polytope can be completely described by nonnegativity, clique and oddhole constraints. It is tperfect if it furthermore has no clique of size 4. For every graph $G$ and every $cinmathbb{Z}_+^{V(G)}$, the weighted chromatic number of $(G,c)$ is the minimum cardinality of a multiset $mathcal{F}$ of stable sets of $G$ such that every $vin V(G)$ belongs to at least $c_v$ members of $mathcal{F}$. We prove that emph{every hperfect linegraph and every tperfect clawfree graph $G$ has the integer roundup property for the chromatic number} : for every nonnegative integer weight $c$ on the vertices of $G$, the weighted chromatic number of $(G,c)$ can be obtained by rounding up its fractional relaxation. In other words, the stable set polytope of $G$ has the integer decomposition property. Another occurrence of this property was recently obtained by Eisenbrand and Niemeier for fuzzy circular interval graphs (extending previous results of Niessen, Kind and Gijswijt). These graphs form another proper subclass of clawfree graphs. Our results imply the emph{existence of a polynomialtime algorithm which computes the weighted chromatic number of tperfect clawfree graphs and hperfect linegraphs}. They also yield a new case of a conjecture of Goldberg and Seymour on edgecolorings. Finally, we settle a problem raised by Shepherd by showing an example of emph{a 3colorable tperfect graph which does not have the integer roundup property}.


214 
A possible connection between girth and total chromatic parameters in cubic graphs 


Simone Dantas, Celina M. H. De Figueiredo, Giuseppe Mazzuoccolo, Myriam Preissmann, Vinicius F. Dos Santos, Diana Sasaki
A cubic graph is said to be Type 1 if it has total chromatic number equal to 4 and


213 
A comparison of inventory policies coupled with a flexible sales and operations planning under long procurement lead times 


Lâm Laurent Lim, Gülgün Alpan, Bernard Penz
A new challenge for industries is to manage efficiently sales and operations in an uncertain and global environment. The sales and operations planning (S&OP) aims to improve the tradeoff between production costs and customer satisfaction. For products with long procurement lead times, new flexibility parameters can be used in the S&OP to improve the supply chain agility and to satisfy efficiently customer demands. In this paper, we consider several inventory policies integrated within a flexible S&OP model. The problem is formulated as a stochastic multiobjective optimization model solved by a simulationoptimization approach. Based on the case study of the automobile manufacturer, Renault, we present a numerical comparative study of the different strategies in terms of system performance. We also provide managerial insights that are particularly relevant to improve the S&OP and inventory management for companies that face uncertain demand, impatient customers and distant sourcing.


212 
A simulationoptimization approach for managing the sales and operations planning in the automotive industry 


Lâm Laurent Lim, Gülgün Alpan, Bernard Penz
Due to the increasing globalization and the distant sourcing, reconciling industrial constraints and sales requirements becomes very challenging for industries facing an uncertain environment and demanding customers. The sales and operations planning (S&OP) is crucial for efficiently balancing production capacities with the volatile market demand. In this article, we propose an original S&OP model in order to improve the tradeoff between the supply chain costs and the customer satisfaction. The problem is formulated as a multiobjective optimization model with epsilonconstraints and is solved by a simulationoptimization approach. Two classes of policies for managing the parts procurement and the flexibility offered to the sales function are presented. The model and the proposed solution are illustrated with the case study of Renault, a French global automobile manufacturer. Several policies and optimization algorithms are compared in terms of system performance and computation time. Managerial insights are derived based on these results.


211 
Issues in the complementary use of simulation and optimization modeling 


AnneLaure Ladier, Allen G. Greenwood, Gülgün Alpan, Halston Hales
Simulation models and discrete optimization models are oftentimes used together in a variety of ways. In this paper, we discuss the issues that modelers must address in cases where simulation models are used to test a discrete mathematical programming optimization model’s performance in a stochastic environment. The issues arise during validation of simulation models, when checking agreement between deterministic optimization results and simulation models operating under deterministic conditions. In our case, the issues are derived from validating simulation models that are used to test the performance of scheduling and resource allocation models (integer and mixedinteger programming optimization models) under various types of uncertainty. While the concerns we describe are from our work in the logistics domain (crossdocking operations), they are relevant to a wide variety of problem domains. In addition to describing the issues, we offer suggestions on how modelers might address the concerns.


210 
Reconciling sales and operations management with distant suppliers in the automotive industry: a simulation approach 


Lâm Laurent Lim, Gülgün Alpan, Bernard Penz
A challenge for car manufacturers is to adjust rapidly and efficiently the production capacities with a volatile market demand and despite distant suppliers. In this paper, we consider a sales and operations planning problem based on the actual situation of Renault, a French global automobile manufacturer. The issue is to find the best tradeoff between sales requirements and industrial constraints while limiting inventories, emergency supplies and keeping delivery lead times reasonable for customers. A new planning method based on flexibility rates is presented. The flexibility rates are defined to limit orders of a given type of vehicles, during a certain period. A simulation model is introduced and captures the dynamics of the sales and operations management. A numerical study has been performed by using industrial data. Results highlight factors that improve system performances and several policies are compared. This research has also relevance for other industries that face long procurement lead times in an uncertain environment.


209 
Additions to Lawler’s minmax cost algorithm: Optimality conditions and uncertainty 


Nadia Brauner, Gerd Finke, Yakov Shafransky, Dzmitry Sledneu
The wellknown O(n2) minmax cost algorithm of Lawler [2] was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. The first one concerns necessary and sufficient conditions for the sequence optimality when all the cost functions are strictly increasing. The second result concerns the scheduling on a single machine under both uncertainty of some job’s parameters and precedence constraints. In the latter problem, each job has an asso ciated nondecreasing cost function of a special (decomposable) form. The cost function for each job depends on the job completion time and on an additional parameter value. The aim is to find a schedule for processing the jobs that is feasible with respect to the given prece dence constraints and that minimizes the maximum cost over all the jobs. The class of the functions under consideration includes known functions such as the maximum lateness and the maximum delivery time. For the problem under uncertainty (where for each job, we know only an interval for possible values of the additional parameter), we derive an O(n2) algorithm for constructing a schedule that minimizes the maximal regret criterion. To obtain this schedule, we use Lawler’s algorithm as a part of our technique.


208 
SemiOnline Bin Stretching with Bunch Techniques 


Michaël Gabay, Vladimir Kotov, Nadia Brauner
We are given a sequence of items that can be packed into $m$ unit size bins and the goal is to assign these items online to m bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 improving the best known algorithm by Kellerer and Kotov with a stretching factor 11/7. Our algorithms has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose.


207 
Complements of nearly perfect graphs 


András Gyárfás, Zhentao Li, Raphael Machado, András Sebő, Nicolas Trotignon
A class of graphs closed under taking induced subgraphs is $\chi$bounded if there exists a function $f$ such that for all graphs $G$ in the class, $\chi(G) \leq f(\omega(G))$. We show that if $\cal C$ is $\chi$bounded by the constant function $f(x)=3$, then $\overline{\cal C}$ is $\chi$bounded by $g(x)=\lfloor\frac{8}{5}x\rfloor$ and this is best possible.


206 
Stability Contract in the Forest Products Supply Chain: Case Study for a Quebec Region 


Bertrand Hellion, Sophie D’Amours, Nadia Lehoux, Fabien Mangione, Bernard Penz
In this paper an industrial case including a papermill and its three suppliers (sawmills) is studied.


205 
Singlemachine production and maintenance: a unified approach 


Gerd Finke, MarieLaure Espinouse, Ahmed GaraAli, Vincent Jost, Julien Moncel
We are presenting a general unifying framework for productionmaintenance systems on a single machine. Several performance criteria are included as well as most of the maintenance systems that are proposed in the literature. No particular analytical functions are required and no new algorithms have to be developed. One may simply utilize standard software for mincost network flow problems.


204 
A polynomial time algorithm for the singleitem lot sizing problem with capacities, minimum order quantities and dynamic time windows 


Bertrand Hellion, Fabien Mangione, Bernard Penz
This paper deals with the singleitem capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows.


203 
Construction of snarks with total chromatic number 5 


Gunnar Brinkmann, Myriam Preissmann, Diana Sasaki
A ktotalcoloring of G is an assignment of k colors to the edges


202 
Fast recognition of doubled graphs 


Frédéric Maffray
Double split graphs form one of the five basic classes in the proof of


201 
Stability contracts between supplier and retailer: a new lot sizing model 


Bertrand Hellion, Fabien Mangione, Bernard Penz
This work explores the relationship between decision makers in a company and


200 
On the excessive [m]index of a tree 


Giuseppe Mazzuoccolo
The excessive [m]index of a graph G is the minimum number of matchings of size m needed to cover the edgeset of G. We call a graph G [m]coverable if its excessive [m]index is finite. Obviously the excessive [1]index is E(G) for all graphs and it is an easy task the computation of the excessive [2]index for a [2]coverable graph. The case m=3 is completely solved by Cariolaro and Fu in 2009. In this paper we prove a general formula to compute the excessive [4]index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]index of an arbitrary graph.


199 
The chromatic number of {P5, K4}free graphs 


Louis Esperet, Laetitia Lemoine, Frédéric Maffray, Grégory Morel
Gyárfás conjectured that for any tree T every Tfree graph G


198 
Shorter Tours by Nicer Ears : 7/5approximation for graphic TSP, 3/2 for the path version, and 4/3 for twoedgeconnected subgraphs 


András Sebő, Jens Vygen
We prove new results for approximating the graphic TSP and some related problems. For the graphic TSP itself, we improve the approximation ratio The key new ingredient of all our algorithms is a special kind of eardecomposition medskip oindent{{f keywords:} traveling salesman problem, graphic TSP, $2$edgeconnected subgraph,


197 
Packing of Rigid Spanning Subgraphs and Spanning Trees 


Joseph Cheriyan, Zoltán Szigeti, Olivier Durand de Gevigney
We prove that every (6k + 2l,2k)connected simple graph contains k rigid and l connected edgedisjoint spanning subgraphs. This implies a theorem of Jackson and Jordán [4] and a theorem of Jordán [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lovász and Yemini [9] saying that every 6connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every 8connected graph packs a spanning tree and a 2connected spanning subgraph; (2) every 14connected graph has a 2connected orientation.


196 
The hunting of a snark with total chromatic number 5 


Diana Sasaki, Simone Dantas, Celina De Figueiredo, Myriam Preissmann
A snark is a cyclically4edgeconnected cubic graph with chromatic index 4. In 1880, Tait proved that the FourColor Conjecture is equivalent to the statement that every planar bridgeless cubic graph has chromatic index 3. The search for counterexamples to the Four Color Conjecture motivated the definition of the snarks.


195 
Securing production resources in decentralized supply chain planning 


Maxime Ogier, VanDat Cung, Julien Boissière
Supply chain optimization is a very complex task when taking into account its inherently decentralized aspect and sustainable development considerations. In order to provide a sustainable supply chain model faithful to reality, this paper presents a two actors supply chain model with a manufacturer and a 3PL provider. Centralized and decentralized planning at tactical level, with lotsizing models, presented by Jung et al. (2008) is studied. This model is extended by including rolling planning horizon, and demand forecast errors, to take into account difficulties of supply chain actors to evaluate future demands. A preliminary experimental study highlights the good economic performance of the decentralized planning and the consequences of demand uncertainty on supply chain total cost. Then, we point out the poor production resource management with rolling horizon planning. Because of social consequences that may result, a new constraint is integrated in the supply chain model : securing production resources. This results in the impossibility to modify the planning on the coming periods. The economic impact of the integration of this social criteria is studied. Results are presented based on deterministic or stochastic demands, and with different rolling horizon length. It points out that securing production resource is not very expensive when planning on a small rolling horizon or with deterministic demands. Various future extensions of this model are also discussed.


194 
Stochastic Scheduling with Impatience to the Beginning of Service 


Alexandre Salch, JeanPhilippe Gayon, Pierre Lemaire
In this paper we discuss a stochastic scheduling problem with impatience to the beginning of service. The impatience of a job can be seen as a due date and a job is considered to be on time if it begins to be processed before its duedate. Processing times and due dates are random variables. Jobs are processed on a single machine with the objective to minimize the expected weighted number of tardy jobs in the class of static list scheduling policies. We derive optimal schedules when processing times and due dates follow different probability distributions. We also study the relation between the problem with impatience to the beginning of service and the problem with impatience to the end of service. Finally, we provide some additional results for the problem with impatience to the end of service.


193 
A polynomial time algorithm to solve the singleitem capacitated lot sizing problem with minimum order quantities and concave costs 


Bertrand Hellion, Bernard Penz, Fabien Mangione
This paper deals with the singleitem capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSPMOQ). In this problem, a demand must be satised at each period t over a planning horizon of T periods. This demand can be satised from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T5) is proposed and it is computationally tested on various instances.


192 
bcoloring of some bipartite graphs 


Mostafa Blidia, Noureddine Ikhlef Eschouf, Frédéric Maffray
A bcoloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the bchromatic number b(G) of a graph G is the largest integer k such that G admits a bcoloring with k colors. We show that every graph of order n, different from a clique, satisfies b(G) ? [n + w(G) 1]/2, where w(G) is the maximum clique size in G, and we give a characterization of bipartite graphs that achieve equality in this bound. Also we show that every graph G satisfies b(G) – chi(G) ? [n/2] – 2, and we deduce a characterization of graphs that achieve this bound. In [2] it was shown that if G is a connected graph of order n ? 5, then for every vertex v of G we have b(Gv) ? b(G) + [n/2] – 2. We confirm this result for an arbitrary graph of order n ? 4 and we conjecture that this bound is attained if and only if G = C4, P4 or 2P2.


191 
On 3colorable P5free graphs 


Frédéric Maffray, Grégory Morel
We consider the class of P5free 3colorable graphs. We give a complete description of the structure of the graphs in that class. We derive a linear time algorithm that tests membership in the class.


190 
Schedulling of washing operations in a hospital sterilization service for minimizing the mean predisinfection excess time of medical devices 


Onur Ozturk, Maria Di Mascolo, MarieLaure Espinouse, Alexia Gouin
After use in operating blocs, medical devices (MD) are sent to the sterilization service. The sterilization process is composed of various steps. In the washing step, after predisinfection, different sets of MD, used for different surgical operations, may be washed together without exceeding washer capacity. It is generally not allowed to split MD sets among several washers. In this paper, we model the washing step as a batch scheduling problem, where MD sets are denoted as jobs having different sizes and different release dates, but equal processing times for the washing. The washing steps of sterilization services generally constitute a bottleneck for the entire sterilization process and long predisinfection times may corrode MD. Hence, the decisions for batching the MD sets and launching washing cycles are crucial in order to minimize the waiting time of MD in the washing step. First, we provide a MILP model for the minimization of mean predisinfection excess time and then a ?constraint model for the minimization of a second criterion which is the number of washing cycles. Afterwards, two heuristics are developed and experimented on the instances inspired from a real case.


189 
Generic algorithms for some decision problems on fasciagraphs and rotagraphs 


Marwane Bouznif, Julien Moncel, Myriam Preissmann
A fasciagraph consists in a sequence of copies of the same graph, each copy being linked to the next one according to a regular scheme. More precisely a fasciagraph is characterized by an integer $n$ (the number of copies or fibers) and a mixed graph $M$. In a rotagraph, the last copy is also linked to the first one. In the literature, similar methods were used to address various problems on rotagraphs and fasciagraphs. The goal of our work is to define a class of decision problems for which this kind of methods works. For this purpose, we introduce the notion of pseudo$d$local $q$properties of fasciagraphs and rotagraphs. For a mixed graph $M$ and a pseudo$d$local $q$property $mathcal{P}$, we propose a generic algorithm for rotagraphs (resp. fasciagraphs) that computes in constant time a closed formula as a boolean function $ au$ (resp. $varphi$) on $mathbb{N}$. For all $n in mathbb{N}$ $ au(n)=1$ (resp. $varphi(n)=1$) if and only if the rotagraph (resp. fasciagraph) of length $n$ based on $M$ satisfies $mathcal{P}$.


188 
MINIMIZING THE TOTAL DURATION OF THE WASHING STEP IN A HOSPITAL STERILIZATION SERVICE 


Onur Ozturk, MarieLaure Espinouse, Maria Di Mascolo, Alexia Gouin
In this paper, we study the problem of minimizing the total duration of the washing operations in hospital sterilization services. After use in operating blocs, reusable medical devices (RMD) are sent to the sterilization service, which is composed of various steps. In the washing step, different sets of RMD, used for different surgeries, may be washed together without exceeding washer capacity. It is generally not allowed to split RMD sets among several washers.


187 
On disjoint paths in acyclic planar graphs 


Guyslain Naves
We give an algorithm with complexity $O(f (R)^{k^2} k^3 n)$ for the integer multiflow problem on instances $(G, H, r, c)$ with $G$ an acyclic planar digraph and $r + c$ Eulerian. Here, $f$ is a polynomial function, $n = V (G)$, $k = E(H)$ and $R$ is the maximum request $max_{h∈E(H)} r(h)$. When $k$ is fixed, this gives a polynomial algorithm for the arcdisjoint paths problem under the same hypothesis.


186 
Toward an Optimal Scan Insertion at the Register Transfer Level 


Lilia Zaourar, Yann Kieffer, Nadia Brauner, Chouki Aktouf
This work shows improvements towards effective consideration of scan presynthesis. A new algorithm is proposed to optimally decide about scan stitching at RTL. Algorithm efficiency is proven through an industrial RTLtoGDS design flow and typical design benchmarks.


185 
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs 


Louis Esperet, Frantisek Kardos, Daniel Kral
Lovasz and Plummer conjectured in the 1970’s that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear bound in the general case.


184 
The chromatic gap and its extremes 


András Gyárfás, András Sebő, Nicolas Trotignon
The chromatic gap is the difference between the chromatic number and the clique number of a graph. Here we investigate gap(n), the maximum chromatic gap over graphs on n vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for gap(n) in terms of Ramsey numbers. For our purposes it is more convenient to work with the covering gap, the difference between the clique cover number and stability number of a graph and this is what we call the gap of a graph. Then gap(n) can be equivalently defined (by switching from a graph to its complement), as the maximum gap over graphs of n vertices. Notice that the wellstudied family of perfect graphs are the graphs whose induced subgraphs have gap zero. Our study is a first step towards better understanding of graphs whose induced subgraphs have gap at most t. The maximum of the (covering) gap and the chromatic gap running on all induced subgraphs will be called perfectness gap. Using alpha(G) for the cardinality of a largest stable (independent) set of a graph G, we define alpha(n) = min alpha(G) where the minimum is taken over trianglefree graphs on n vertices. It is easy to observe that alpha(n) is essentially an inverse Ramsey function, defined by the relation R(3, alpha(n)) ≤ n < R(3, alpha(n)+1). The central notions in our investigations are the gapcritical and the gapextremal graphs. A graph G is gapcritical if for every proper induced subgraph H of G, gap(H) < gap(G) and gapextremal if it is gapcritical with as few vertices as possible (among gapcritical graphs of the same gap). The strong perfect graph theorem, solving a long standing conjecture of Berge that stimulated a broad area of research, states that gapcritical graphs with gap 1 are the holes (chordless odd cycles of length at least five) and antiholes (complements of holes). The next step, the complete description of gapcritical graphs with gap 2 would probably be a very difficult task. As a very first step, we prove that there is a unique 2extremal graph, 2C5, the union of two disjoint (chordless) cycles of length five. In general, for t ≥ 0, we denote by s(t) the smallest order of a graph with gap t and we call a graph is textremal if it has gap t and order s(t). It is tempting to conjecture that s(t) = 5t with equality for the graph tC5. However, for t ≥ 3 the graph tC5 has gap t but it is not gapextremal (although gapcritical). We shall prove that s(3) = 13, s(4) = 17 and s(5) is 20 or 21. Somewhat surprisingly, after the uncertain values s(6) in {23, 24, 25}, s(7) in {26, 27, 28}, s(8) in {29, 30 , 31}, s(9) in {32, 33} we can show that s(10) = 35. On the other hand we can easily show that s(t) is asymptotically equal to 2t, that is, gap(n) is asymptotic to n/2. According to our main result the gap is actually equal to ceiling of n/2 – alpha(n), unless n is in an interval [R, R + 14] where R is a Ramsey number, and if this exception occurs the gap may be larger than this value by only a small constant (at most 3). The definition of s(t) does not change if we replace (covering) gap by chromatic gap, so it can in fact be defined with the perfectness gap as well: it is the smallest order of a graph with perfectness gap equal to t.


183 
Disruption management for commercial aviation, a mixed integer programming approach 


Julien Darlay, LouisPhilippe Kronek, Susann Schrenk, Lilia Zaourar
In this paper we describe our approach to the airline disruption problem which was the topic of the ROADEF’09 challenge. The aim of the challenge was to reassign aircrafts and passengers simultaneously in case of disruption, w.r.t. maintenance constraints. We decompose the problem into two main steps: reassignment of aircrafts on flights, and reaccommodation of passengers on operated flights. Both steps take profit of the initial optimized plan, such as passengers are already involved in aircraft reassignment. These steps are simply modelled as multicommodity network flows with side constraints and solved using a MIPsolver. We report the numerical results on the instances provided during that challenge. These results have been quite improved since the end of the challenge with just a little modification in our program.


182 
Dense and sparse graph partition 


Julien Darlay, Nadia Brauner, Julien Moncel
In a graph G = (V, E), the density is the ratio between the number of edges E and the number of vertices V. This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion, the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NPhard by giving a reduction from graphkcolorability. Additionally, we give a polynomial time algorithm for the special case of trees.


181 
Polynomial time algorithms for makespan minimization on one machine with forbidden start and completion times 


Christophe Rapine, Nadia Brauner
We consider independent jobs to sequence on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed neither to start not to complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive a quite fast algorithm to find such a schedule, based on an hybridization between list algorithm and local exchange. We then improve our approach to propose a strongly polynomial time algorithm under a High Multiplicity encoding. As a corollary minimizing the makespan for a constant number of forbidden instants is polynomial.


180 
Comparaison de différentes formulations de conception de réseaux pour un problème de transport de fret avec gestion de véhicules. 


Susann Schrenk, Teodor Gabriel Crainic, Cung VanDat, Gerd Finke
Dans cet article, on s’intéresse à l’étude de la maximisation du profit d’un transporteur de fret. Ce problème intègre la gestion des flux de véhicules simultanément à celle des flux de marchandises. Nous proposons deux modèles linéaires en nombres entiers, l’un fondé sur des variables arcs pour les véhicules, l’autre sur des variables chemins pour les véhicules, les deux avec des variables arcs pour les marchandises. La comparaison expérimentale de ces deux modèles indique que la formulation « chemin » a une bien meilleure relaxation linéaire que la formulation « arc », réputée faible. Cette dominance est également prouvée par une comparaison théorique des deux modèles.


179 
Identical coupled task scheduling: polynomial complexity of the cyclic case 


Vassilissa LehouxLebacque, Nadia Brauner, Gerd Finke
Coupled task problems arise in connection with radar systems. For the trans mission and reception of an electromagnetic pulse the radar (the processor) has to execute two tasks that are separated by some fixed time interval. Most of the com plexity issues for scheduling a set of such pairs of twooperation tasks have been settled. However, the complexity status is still unknown for the identical coupled task problem, where multiple copies of a single coupled task are to be processed. The purpose of this article is prove the polynomial complexity of this problem in the cyclic case.


178 
Single Machine Scheduling with Small OperatorNonAvailability Periods 


C. Rapine, N. Brauner, G. Finke, V. Lebacque
Through an industrial application, we were confronted with the planning of experiments where human intervention of a chemists is required to handle the starting and termination.


177 
The hardness of routing two pairs on one face 


Guyslain Naves
We prove the NPcompleteness of the integer multiflow problem in planar graphs, with the following restrictions: there are only two edges of demand, both lying on the infinite face of the routing graph. It solves a question from Müller. We also give a directed version with only two terminals, and a directed acyclic version, both we only two arcs of demand.


176 
Ramseytype results for Gallai colorings 


András Gyárfás, Gábor Sárközi, András Sebő, Stanley Selkow
A Gallaicoloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallaicolorings occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper) or information theory. Gallaicolorings extend 2colorings of the edges of complete graphs. They actually turn out to be close to 2colorings – without being trivial extensions. Here we give a method to extend some results on 2colorings to Gallaicolorings, among them known and new, easy and difficult results.


175 
Asteroids in rooted and directed path graphs 


Kathie Cameron, Chinh Hoàng, Benjamin Lévêque
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two nonadjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertexdisjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.


174 
Reusable containers within reverse logistic context 


Chandoul Afif, VanDat Cung, Fabien Mangione
Due to economic and environmental constraints, many organizations have started to ship their products in reusable containers such as plastic pallets, boxes and crates. Minimizing the total flow cost arising from reusable containers is a major problem for these organizations. In this paper we will focus on the modeling of this problem as a network flow, and the proposal of an appropriate resolution method. This resolution method will allow us to better understand the system behavior and can be an important tool for studying related problems, such as dimensioning and purchasing policy.


173 
Path partitions, cycle covers and max kchromatic subgraphs: some known, some forgotten, some proven conjectures and integer decomposition of coflows 


András Sebő
We first present pairs of assertions on path partitions in arbitrary digraphs, and on cycle covers in strongly connected graphs, connecting both objects to maximum $k$chromatic subgraphs. We select analogies: statements that hold for path partitions and at least do not admit a counterexample for cycle covers, and vice versa.


172 
On bcolorings in regular graphs 


Mostafa Blidia, Frédéric Maffray, Zoham Zemir
We call “natural editing of algebraic expressions” the editing of algebraic expressions in their natural representation, the one that is used on paper and blackboard. This is an issue we have investigated in the Aplusix project, a project which develops a system aiming at helping students to learn algebra. The paper summarises first this project. Second it defines the notion of algebraic expression, and of representation of algebraic expression. After an exploration of 20 software systems which represent and edit algebraic expressions, the idea of natural editing of algebraic expressions (insertion, deletion, selection, cut, copy, paste, drag and drop) is presented, leading to the notion of “smart editor”.


171 
Characterization of bgammaperfect graphs 


Mostafa Blidia, IkhlefEschouf Noureddine, Frédéric Maffray
A bcoloring is a proper coloring of the vertices of a graph such that each color class has a vertex that is adjacent to a vertex of every other color, and the bchromatic number b(G) of a graph G is the largest k such that G admits a bcoloring with k colors. A Grundy coloring is a proper coloring with integers 1, 2, …, such every vertex has a neighbor of each color smaller than its own color, and the Grundy number gamma(G) of a graph G is the largest k such that G admits a Grundy coloring with k colors. An acoloring is a proper coloring of the vertices of a graph such that the union of any two color classes is not an independent set, and the achromatic number psi(G) of a graph G is the largest k such that G admits an acoloring with k colors. A graph is bgammaperfect if b(H)=gamma(H) holds for every induced subgraph of G. We study the relationship between b and gamma and characterize bgammaperfect graphs as a special subclass of P_4free graphs. We also show how to compute b in polynomial time for every P4free graph. We also characterize bpsiperfect graphs.


170 
A Decomposition Approach solving a Large Scale Service Network Design with Asset Management problem 


Nicolas Teypaz, Susann Schrenk, VanDat Cung
In this paper, we address a complete freight transportation problem. The objective function consists of maximizing the carrier profit. It is not necessary to satisfy all demands but profitable demands should be satisfied globally or partially. The carrier needs to ensure a return on his vehicle investment: his vehicles must be neither under nor overused. To tackle this industrial problem, we present a model based on a formulation of the Service Network Design with Asset Management problem. Due to the difficulty of finding optimal solutions to this problem, we propose a decomposition of the problem into three main steps: construction of the network, filling vehicles with commodities, construction of the vehicle planning. The resolution of these steps involves heuristic schemes, Mixed Integer Programming and Constraint Programming. We consider different methods for solving these steps and whether to allow transhipment. To evaluate the model and the solution algorithms, we produced instances based on a study of real data. The results show that the methods are robust without transhipment and that transhipment can improve profit.


169 
Natural Editing of Algebraic Expressions 


JeanFrançois Nicaud, Denis Bouhineau
We call “natural editing of algebraic expressions” the editing of algebraic expressions in their natural representation, the one that is used on paper and blackboard. This is an issue we have investigated in the Aplusix project, a project which develops a system aiming at helping students to learn algebra. The paper summarises first this project. Second it defines the notion of algebraic expression, and of representation of algebraic expression. After an exploration of 20 software systems which represent and edit algebraic expressions, the idea of natural editing of algebraic expressions (insertion, deletion, selection, cut, copy, paste, drag and drop) is presented, leading to the notion of “smart editor”.


168 
Graph transformations preserving the stability number 


Benjamin Lévêque, Dominique De Werra
We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.


167 
Multiflow Feasability : an Annotated Tableau 


Guyslain Naves, András Sebő
We provide a tableau of 189 entries and some annotations presenting the computational complexity of integer multiflow feasibility problems; 25 entries remain open. The tableau is followed by an introduction to the field, providing more problems and reproving some results with new insights, simple proofs, or slight sharpenings motivated by the tableau, paying particular attention to planar (di)graphs with terminals on the boundary. Last, the theorems that played a keyrole in establishing the tableau are listed.


166 
Characterizing path graphs by forbidden induced subgraphs 


Benjamin Lévêque, Frédéric Maffray, Myriam Preissmann
A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property.


165 
Graph decomposition into paths under length constraints 


Nicolas Teypaz, Christophe Rapine
Given 2 integers a ? b, we define an (a, b)decomposition of a graph G = (V , E ) as a partition of E into paths where the length of each path lies between a and b. In this definition paths are requested to be simple but not necessarily elementary. In other words an (a, b)decomposition corresponds to a partition E1 , . . . , Ek of E with a ? ¦Ei ¦ ? b for all i, and such that each induced subgraph (Vi , Ei ) admits an Eulerian path. In this paper we investigate the complexity of the (a, b)decomposition problem. We give a characteri zation of (2, b)decomposable graphs, from which it is possible to decide in linear time the (2, b)decomposition problem. When a ? 3, we identify 2 classes of graphs, trees and Eulerian graphs, for which the (a, b)decomposition problem remains polynomial. However we prove that the (3, 3)decomposition problem is N P complete, even on bipartite graphs. We give some evidence to conjecture that the more general Hdecomposition problem into a given family H = {H1 , . . . , Hn } of connected graphs is N P complete if and only if all Hi decomposition problems are N P complete.


164 
Alternatives for Testing Total Dual Integrality 


Edwin O’Shea, András Sebő
In this paper we provide characterizing properties of TDI systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a testset for the system’s dual integer programs where all test vectors have positive entries equal to $1$. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by squarefree monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here. In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.


163 
Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility 


Nadia Brauner, Guyslain Naves
We consider a scheduling problem that arises from an industrial application in chemical experimentations, where a single machine can process a fixed number of compatible jobs simultaneously. The precedence graph is restricted to be a disjoint union of chains, and the compatibility constraints are given by a partition of the tasks. Nevertheless, with these restrictions we prove the NPcompleteness of the problem when the machine has a capacity of two, implying the difficulties for greater capacities. We also present a short proof for an infinite capacity. Our results also show the NPcompleteness of the {sc DSupersequence} problem, even when there are only two kinds of strings. We show polynomiality results when the number of chains in the precedence graph is fixed or when each chain has only two jobs. Results are summarized in a table given at the end of the article.


162 
Recent results on wellbalanced orientations 


Attila Bernáth, Satoru Iwata, Tamás Király, Zoltán Király, Zoltán Szigeti
In this paper we consider problems related to NashWilliams’ Strong Orientation Theorem and OddVertex Pairing Theorem. These theorems date to 1960 and up to now not much is known about their relationship to other subjects in graph theory. We investigated many approaches to find a more transparent proof for these theorems and possibly generalizations of them. In many cases we found negative answers: counterexamples and $NP$completeness results. For example we show that the weighted and the degreeconstrained versions of the wellbalanced orientation problem are $NP$hard. We also show that it is $NP$hard to find a minimum cost feasible oddvertex pairing or to decide whether two graphs with some common edges have simultaneous wellbalanced orientations or not. NashWilliams’ original approach was to define bestbalanced orientations with feasible oddvertex pairings: we show here that not every bestbalanced orientation can be obtained this way. However we prove that in the global case this is true: every smooth $k$arcconnected orientation can be obtained through a $k$feasible oddvertex pairing. The aim of this paper is to help to find a transparent proof for the Strong Orientation Theorem. In order to achieve this we propose some other approaches and raise some open questions, too.


161 
On minimally bimperfect graphs 


Chinh Hoàng, Cláudia Linhares Sales, Frédéric Maffray
A bcoloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes. The bchromatic number of a graph $G$ is the largest integer $k$ such that $G$ admits a bcoloring with $k$ colors. A graph is bperfect if the bchromatic number is equal to the chromatic number for every induced subgraph $H$ of $G$. A graph is minimally bimperfect if it is not bperfect and every proper induced subgraph is bperfect. We give a list ${cal{F}}$ of minimally bimperfect graphs, conjecture that a graph is bperfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for several classes of graphs, namely diamondfree graphs, and graphs with chromatic number at most three. Une bcoloration est une coloration des sommets d’un graphe telle que chaque couleur contient un sommet qui a des voisins dans toutes les autres couleurs. Le nombre bchromatique d’un graphe est le plus grand entier k tel que le graphe ait une bcoloration en k couleurs. Un graphe est bparfait si, pour chaque sousgraphe induit H de G, le nombre bchromatique de H est égal à son nombre chromatique habituel. Nous donnons une liste de 22 graphes minimalement bimparfaits et conjecturons qu’un graphe est bparfait si et seulement si il ne contient pas un graphe de cette liste. Nous démontrons cette conjecture dans le cas des graphes sans diamants et des graphes 3colorable.


160 
Operator NonAvailability Periods 


N. Brauner, G. Finke, V. LehouxLebacque, C. Rapine, C. Potts, V. Strusevich
In scheduling literature, the notion of machine nonavailability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the weekends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator nonavailability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling algorithms.


159 
Optimizing Diversity 


Yannick Frein, Benjamin Lévêque, András Sebő
We consider the problem of minimizing the size of a family of sets G such that every subset of {1; … ; n} can be written as a disjoint union of at most k members of G , where k and n are given numbers. This problem originates in a realworld application aiming at the diversity of industrial production. At the same time, the minimum of ¦G ¦ so that every subset of {1; … ; n} is the union of two sets in G has been asked by Erdõs and studied recently by Füredi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n; k) for which n le 3 k holds, and some individual values of n and k.
