Alain Hertz
RetourPublications
Cahiers du GERAD
The arithmetic-geometric index is a newly proposed degree-based graph invariant in mathematical chemistry. We give a sharp upper bound on the value of this ...
référence BibTeX
We consider the set of graphs that can be constructed from a one-vertex graph by repeatedly adding a clique or a stable set linked to all or none of the vert...
référence BibTeX
Tactical wireless networks are used in cases where standard telecommunication networks are unavailable or unusable, e.g. disaster relief operations. We fully...
référence BibTeX
Recommender systems provide personalized recommendations to their users for items and services. They do that using a model that is tailored to each user to i...
référence BibTeX
Le Douzième atelier de résolution de problèmes industriels de Montréal, qui eut lieu du 22 au 26 août 2022, fut organisé conjointement par le Centre de reche...
référence BibTeX
Recommender systems provide recommendations to their users for items and services by creating a model tailored to each user to infer their preferences based ...
référence BibTeX
We investigate the ratio \(\mathcal{I}(G)\)
of the average size of a maximal matching to the size of a maximum matching in a graph G. If many maximal mat...
Distance metric learning algorithms aim to appropriately measure similarities and distances between data points. In the context of clustering, metric learnin...
référence BibTeX
A coloring of a graph is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings are equivalent if they indu...
référence BibTeX
We study the average number \(A(G)\)
of colors in the non-equivalent colorings of a graph \(G\)
. We show some general properties of this graph invariant ...
The Bell numbers count the number of different ways to partition a set of \(n\)
elements while the graphical Bell numbers count the number of non-equivalen...
Decycling bipartite graphs
Let \(G=(V,E)\)
be a graph and let \(S\subseteq V\)
be a subset of its vertices. If the subgraph of \(G\)
induced by \(V\setminus S\)
is acyclic, the...
Given a set \(\mathcal{R}\)
of m disjoint finite regions in the 2-dimensional plane, all regions having polygonal boundaries, and given a set `(\mathc...
Les algorithmes de partitionnement de données aident à identifier des sous-groupes homogènes en ce sens que les données de chaque groupe partagent des caract...
référence BibTeXAn exact dynamic programming algorithm for the precedence-constrained class sequencing problem
This article discusses the precedence-constrained class sequencing problem (PCCSP). In scheduling terms, this is a one-machine scheduling problem with preced...
référence BibTeXGraph colouring variations
We consider three colouring problems which are variations of the basic vertex-colouring problem, and are motivated by applications from various domains. We g...
référence BibTeX
Recommender systems make use of different sources of information for providing users with recommendations of items. Such systems are often based on collabor...
référence BibTeX
The eccentric connectivity
index of a connected graph \(G\)
is the sum over all vertices \(v\)
of the product \(d_G(v)e_G(v)\)
, where \(d_G(v)\)
is ...
The eccentricity of a vertex \(v\)
in a graph \(G\)
is the maximum distance
between \(v\)
and any other vertex of \(G\)
. The diameter of a graph `(...
A graceful difference labeling (gdl for short) of a directed graph \(G\)
with vertex set \(V\)
is a bijection `(f:V\rightarrow{1,\ldots,\vert V\vert}...
Given a directed graph \(G=(V,A)\)
, capacity and cost functions on \(A\)
, a root \(r\)
, a subset \(T \subset V\)
of terminals, and an integer \(k\)
...
Most papers on digital advertising focus on the point of view of Internet companies such as Google and Microsoft, and were written by people working for thos...
référence BibTeX
We consider the problems of determining the metric dimension and the minimum cardinality of doubly resolving sets in \(n\)
-cubes.
Most heuristics develope...
Nous donnons des conditions nécessaires et suffisante pour l'existence d'un graphe simple, ou d'un graphe connexe simple, ayant des nombres donnés `(m_{ij}...
référence BibTeX
This article discusses the problem of unloading a sequence of boxes from a single conveyor line with a minimum number of moves. The problem under study is ef...
référence BibTeX
Étant donné un graphe \(G\)
complet, orienté, avec des poids sur les sommets et les arcs,
une \(k\)
-coloration \(\theta\)
-impropre de \(G\)
est une...
Le problème de la détermination du plus grand sous-graphe \(k\)
-colorable (\(k\)
-MCSP)
consiste à colorer autant de sommets que possible avec au plus `...
Dans cet article nous étudions le problème de concevoir un réseau de collecte pour un parc éolien, dans le cas où la localisation des turbines et des câble...
référence BibTeX
Given a graph \(G=(V,E)\)
with a root \(r\in V\)
, positive capacities \(\{c(e) | e\in E\}\)
, and non-negative lengths \(\{\ell(e) | e\in E\}\)
, the m...
This paper addresses the problem of minimizing the number of moves to unload a set of boxes off a gravity conveyor by a forklift. If the input data is known ...
référence BibTeX
An edge-coloring of a graph \(G=(V,E)\)
is a function \(c\)
that assigns an integer \(c(e)\)
(called color) in \(\{0,1,2,\dotsc\}\)
to every edge `(...
In recent years, a growing interest has been observed in research on RNA (ribonucleic acid), primarily due to the discovery of the role of RNA molecules in ...
référence BibTeX
Écrire un texte de qualité est un processus complexe. Plusieurs domaines d'études se penchent sur les possibilités d'analyse des pratiques d'écriture des bon...
référence BibTeX
Given a complete directed graph \(G\)
with weights on the vertices and on the arcs, a \(\theta\)
-improper \(k\)
-coloring is an assignment of at most `...
An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The **dominating induced matchin...
référence BibTeX
In the present paper, we are interested in bounding differences between graph invariants as well as in characterizing the corresponding extremal graphs. This...
référence BibTeX
Deux colorations des sommets d'un graphe sont dites équivalentes si elles correspondent à la même partition de l'ensemble des sommets en classes de couleurs....
référence BibTeX
Until recently, graph coloring being a computationally difficult problem, completely dynamic channel allocation was not considered in large scale networks. T...
référence BibTeX
Une coloration des arêtes d'un graphe \(G\)
est une fonction qui attribue un entier (appelé couleur) à chaque arête de \(G\)
de telle sorte que les arête...
L'algorithme RLF (Recursive Largest First) est l'un des plus populaires parmi les heuristiques gloutonnes pour le problème de la coloration des sommets d'un ...
référence BibTeXChromatic Scheduling
Variations and extensions of the basic vertex-colouring and edge-colouring models have been developed to deal with increasingly complex scheduling problems. ...
référence BibTeX
A graph \(G = (V,E)\)
is \(r\)
-equitably \(k\)
-colorable if there exists a partition of \(V\)
into \(k\)
independent
sets `(V1, V2, \ldots, V_k...
We study the number \({\cal{P}}(G)\)
of non-equivalent ways of coloring a given graph \(G\)
. We show some similarities and differences between this graph...
A Repeated Sequential Elimination Algorithm for Finding an Upper Bound on the Clique Number
In this paper a new procedure for finding an upper bound on the clique number of a given graph is described. Gendron, Hertz and St-Louis (2008) proposed a se...
référence BibTeX
In this paper, we study the problem introduced by Baptiste et al. (2011) of minimizing the number of steps to unload a set of boxes off a gravity conveyor. W...
référence BibTeX
Given a directed graph with weights on the vertices and on the arcs, a θ-improper <i>k</i>-coloring is an assignment of at most <i>k</i> different colo...
référence BibTeX
Given a graph <i>G</i>, an integer <i>k</i>, and a cost <i>c<sub>uv</sub></i> associated with all pairs <i>uv</i> of non-adjacent vertices in <i>G</i>, the ...
référence BibTeX
In this article we study a network design problem that arises in the exploitation of wind energy. We formulate this problem as a mixed integer programming ...
référence BibTeX
Soit \(G\)
un graphe connexe, \(n\)
l'ordre de \(G\)
, et \(f\)
(resp. \(t\)
)
l'ordre maximum d'une forêt induite (resp. d'un arbre induit) dans
`...
An <i>r</i>-equitable <i>k</i>-coloring <i>c</i> of a graph <i>G=(V,E)</i> is a partition of <i>V</i> into <i>k</i> stable sets <img src="/cgi-bin/mimetex.cg...
référence BibTeX
We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the ...
référence BibTeX
In this paper we study a variant of the Capacitated Team Orienteering Problem (CTOP), that is the problem where a fleet of vehicles, each with a constraint...
référence BibTeX
In this paper we study the capacitated team orienteering problem where split deliveries are allowed. A set of potential customers is given, each associated w...
référence BibTeX
La confection de calendriers sportifs dans le milieu scolaire québécois est une tâche complexe à laquelle la Fédération Québécoise du Sport Étudiant (FQSE) d...
référence BibTeX
A total dominating set in a digraph <i>G</i> is a subset <i>W</i> of its vertices such that every vertex of <i>G</i> has an immediate successor in <i>W</i>. ...
référence BibTeX
A <i>k</i>-edge-coloring of a graph <i>G=(V,E)</i> is a function <i>c</i> that assigns an integer <i>c(e)</i> (called color) in <i>{0,1, ..., k-1}</i> to eve...
référence BibTeX
We consider an inventory routing problem in discrete time where a supplier has to serve a set of customers over a time horizon. A capacity constraint for th...
référence BibTeX
A profit and a demand are associated with each arc of a set of profitable arcs of a given graph. A travel time is associated with each arc of the graph. A fl...
référence BibTeX
A magnet is a pair <i>u,v</i> of adjacent vertices such that the proper neighbours of <i>u</i> are completely linked to the proper neighbours of <i>v</i>. It...
référence BibTeX
With the help of the Graffiti system, Fajtlowicz conjectured around 1992 that the average distance between two vertices of a connected graph <i>G</i> is at ...
référence BibTeX
Le texte qui suit est un chapitre du livre intitulé <i>Fourmis artificielles, des bases algorithmiques aux concepts et réalisations avancés</i>, Nicolas Monm...
référence BibTeX
In this paper we present a simple technique that uses background information to improve mining the frequent patterns of structured data. This technique uses ...
référence BibTeXSyGMA: Reducing Symmetry in Graph Mining
While recent algorithms for mining the frequent subgraphs of a database are efficient in the general case, these algorithms tend to do poorly on databases th...
référence BibTeX
Flexibility in workforce planning is one of the best ways to respond to fluctuations of the demand. This paper proposes a flexible mixed integer linear pro...
référence BibTeX
<p> Given a graph <i>G=(V,E)</i> with strictly positive integer weights <img src="/cgi-bin/mimetex.cgi?\omega_i"> on the vertices <img src="/cgi-bin/mimete...
référence BibTeX
This paper proposes to use local search inside filtering algorithms of combinatorial structures for which achieving a desired level of consistency is too c...
référence BibTeXOn a Reduction of the Interval Coloring Problem to a Series of Bandwidth Coloring Problems
Given a graph <img src="/cgi-bin/mimetex.cgi?G=(V,E)"> with strictly positive integer weights <img src="/cgi-bin/mimetex.cgi?\omega_i"> on the vertices <img ...
référence BibTeX
Given a class of graphs <img src="/cgi-bin/mimetex.cgi?\mathcal{F}">, a forbidden subgraph characterization (FSC) is a set of graphs <img src="/cgi-bin/mimet...
référence BibTeX
In this paper we study the Capacitated Team Orienteering and Profitable Tour Problems (CTOP and CPTP). The interest in these problems comes from recent devel...
référence BibTeX
We consider the bandwidth coloring problem, a generalization of the well-known graph coloring problem. For the latter problem, a classical theorem, discover...
référence BibTeX
An edge coloring of a graph <img src="/cgi-bin/mimetex.cgi?G = (V,E)"> is a function <img src="/cgi-bin/mimetex.cgi?c:E \rightarrow N"> that assigns a co...
référence BibTeX
We consider the problem of assigning patients to nurses for home care services. The aim is to balance the workload of the nurses while avoiding long travels...
référence BibTeXUsing Meta-Heuristics to Find Minimal Unsatisfiable Subformulas in Satisfiability Problems
In this paper, we propose efficient algorithms to extract minimal unsatisfiable subsets of clauses or variables in unsatisfiable propositional formulas. Suc...
référence BibTeX
We consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bou...
référence BibTeXVariable Space Search for Graph Coloring
Let <i>G = (V,E)</i> be a graph with vertex set <i>V</i> and edge set <i>E</i>. The <i>k</i>-coloring problem is to assign a color (a number chosen in {1,.....
référence BibTeX
Given a set of timetabled tasks, the multi-depot vehicle scheduling problem is a wellknown problem that consists of determining least-cost schedules for veh...
référence BibTeX
The problem retained for the ROADEF’99 international challenge was an inventory management problem for a car rental company. It consists in managing a given...
référence BibTeX
We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy ...
référence BibTeXThe Metric Cutpoint Partition Problem
Let <img src="/cgi-bin/mimetex.cgi?G = (V,E,w)"> be a graph with vertex and edge sets <img src="/cgi-bin/mimetex.cgi?V"> and <img src="/cgi-bin/mimetex.cgi?E...
référence BibTeX
We analyze a territorial approach to deliver nursing home care services to a territory public health. We present the case of the CSSS assigned to Côte-des-N...
référence BibTeXThe Metric Bridge Partition Problem
Let <i>G = (V,E,w)</i> be a graph with vertex and edge sets <i>V</i> and <i>E</i>, respectively, and <i>w : E</i> <img src="/cgi-bin/mimetex.cgi?\rightarrow"...
référence BibTeX
The Team Orienteering Problem (TOP) is the generalization to the case of mul- tiple tours of the Orienteering Problem, known also as Selective Traveling Sal...
référence BibTeX
We consider a crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a ...
référence BibTeXA Note on Tree Realizations of Matrices
It is well known that each tree metric <i>M</i> has a unique realization as a tree, and that this realization minimizes the total length of the edges among ...
référence BibTeX
Nous décrivons les méta-heuristiques couramment utilisées en optimisation, avec pour objectif de guider toute personne désirant adapter une méta-heuristique...
référence BibTeX
This article reviews some of the best metaheuristics proposed in recent years for the Vehicle Routing Problem. These are based on local search, on populatio...
référence BibTeX
In the present paper we review the method of augmenting graphs, which is a general approach to solve the maximum independent set problem. Our objective is th...
référence BibTeX
The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard probl...
référence BibTeX
<i>Tabucol</i> is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a fixed number <i>k</...
référence BibTeX
This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph <i>G</i>, and demonstrates how these critical subgraphs ...
référence BibTeX
Let <i>G</i>=(<i>V,E</i>) be a graph with vertex set <i>V</i> and edge set <i>E</i>. The <i>k</i>-colouring problem is to assign a colour (a number chosen ...
référence BibTeX
The augmenting chain technique has been applied to solve the maximum stable set problem in the class of line graphs (which coincides with the maximum matchin...
référence BibTeX
Given a finite set <i>E</i> and a family <i>F</i>={<i>E</i><sub>1</sub>,...,<i>E<sub>m</sub></i>} of subsets of <i>E</i> such that <i>F</i> covers <i>E</i>...
référence BibTeX
We describe a tabu search algorithm for the vehicle routing problem with split deliveries. At each iteration, a neighbour solution is obtained by removing a ...
référence BibTeX
The 18<sup>th</sup> EURO Summer/Winter Institute (ESWI XVIII) took place during the spring 2000 in Switzerland. The topic of ESWI XVIII, "Meta-heuristics in ...
référence BibTeXRecent Trends in Arc Routing
Arc routing problems (ARPs) arise naturally in several applications where streets require maintenance, or customers located along road must be serviced. The ...
référence BibTeX
Finding augmenting chains is in the heart of the maximum matching problem, which is equivalent to the maximum stable set problem in the class of line graphs...
référence BibTeX
The complexity status of the maximum stable set problem in the class of <i>P</i><sub>5</sub>-free graphs is unknown. In this paper, we first propose a chara...
référence BibTeX
The maximum stable set problem is NP-hard, even when restricted to <i>banner</i>-free graphs. In this paper, we use the augmenting graph approach to attack ...
référence BibTeX
This article reports on some recent algorithmic development for the <i>Rural Postman Problem</i> (CPP) and for the <i>Capacitated Arc Routing Problem</i> (C...
référence BibTeX
Given a graph <i>G</i> with <i>n</i> vertices and stability number <img src="alpha.gif" align=bottom>(<i>G</i>), Turán's theorem gives a lower bound on the ...
référence BibTeX
We study empirically the topology of the local minima of the 3-SAT problem. In particular, we analyze the size of the plateaus, their altitude, their attrac...
référence BibTeXChopping Graphs
Chopping a graph <i>G</i> means removing one edge from each connected component of <i>G</i> in parallel, and repeating this until no edges remain. The requi...
référence BibTeX
This article considers a tool loading problem whose objective is to minimize the number of tool switches over time in order to process several parts on a fl...
référence BibTeXSplitting Trees
Splitting a tree is defined as removing all edges of a chain and disconnecting one from the other edges incident with that chain. Splitting a forest is simu...
référence BibTeX
Given a binary matrix <i>E</i>, the Seriation Problem consists of determining a permutation of the rows of <i>E</i> minimizing the sum over all columns of t...
référence BibTeX
In a first attempt to explain the good behavior of local improvement heuristics (such as Tabu Search and Simulated Annealing) for the <i>k</i>-coloring prob...
référence BibTeX
We derive from Boolean methods a transformation which, when it can be applied, builds from a graph <i>G =</i> (<i>V,E</i>) a new graph <i>G'=</i> (<i>V',E'<...
référence BibTeX
For a weighted graph <i>G =</i> (<i>V,E</i>), the maximum weighted <i>k</i>-coloring problem is to color a set of vertices of maximum weight using <i>k</i> ...
référence BibTeX
We describe two new classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedu...
référence BibTeX
The purpose of this paper is to describe a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algori...
référence BibTeX
A bounded vertex coloring of a graph <i>G</i> is a usual vertex coloring in which each color is used at most <i>k</i> times (where <i>k</i> is a given numbe...
référence BibTeX
We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process ...
référence BibTeX
We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure which...
référence BibTeX