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 ...

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...

Tactical wireless networks are used in cases where standard telecommunication networks are unavailable or unusable, e.g. disaster relief operations. We fully...

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...

The Twelfth Montreal IPSW took place on August 22-26, 2022, and was jointly organized by the Centre de recherches mathématiques (CRM) and the Institute for D...

Recommender systems provide recommendations to their users for items and services by creating a model tailored to each user to infer their preferences based ...

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...

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...

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...

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...

Clustering algorithms help identify homogeneous subgroups from data. In some cases, additional information about the relationship among some subsets of the d...

This article discusses the precedence-constrained class sequencing problem (PCCSP). In scheduling terms, this is a one-machine scheduling problem with preced...

We consider three colouring problems which are variations of the basic vertex-colouring problem, and are motivated by applications from various domains. We g...

Recommender systems make use of different sources of information for providing users with recommendations of items. Such systems are often based on collabor...

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...

We consider the problems of determining the metric dimension and the minimum cardinality of doubly resolving sets in \(n\)-cubes. Most heuristics develope...

Necessary and sufficient conditions are provided for the existence of a simple graph, or a simple connected graph with given numbers \(m_{ij}\) of edges ...

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...

Given a complete directed graph \(G\) with weights on the vertices and on the arcs, a \(\theta\)-improper \(k\)-coloring of \(G\) is an assignment of...

The maximum \(k\)-colorable subgraph problem (\(k\)-MCSP) is to color as many vertices as possible with at most \(k\) colors, such that no two adjacent...

In this article we consider a real-world problem submitted to us by the Hatch company. This problem consists of designing a collection network for a wind f...

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 ...

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 ...

Writing is a complex process and it is difficult to know how to write well in order to make a good text. Many fields and techniques are combined to analyze h...

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...

In the present paper, we are interested in bounding differences between graph invariants as well as in characterizing the corresponding extremal graphs. This...

Two vertex colorings of a graph \(G\) are equivalent if they induce the same partition of the vertex set into color classes. The graphical Bell number `(...

Until recently, graph coloring being a computationally difficult problem, completely dynamic channel allocation was not considered in large scale networks. T...

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 `(...

The Recursive Largest First (RLF) algorithm is one of the most popular greedy heuristics for the vertex coloring problem. It sequentially builds color clas...

Variations and extensions of the basic vertex-colouring and edge-colouring models have been developed to deal with increasingly complex scheduling problems. ...

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...

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...

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...

Given a directed graph with weights on the vertices and on the arcs, a &theta;-improper <i>k</i>-coloring is an assignment of at most <i>k</i> different colo...

Given a graph <i>G</i>, an integer <i>k</i>, and a cost <i>c_uv</i> associated with all pairs <i>uv</i> of non-adjacent vertices in <i>G</i>, the ...

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 ...

Let \(G\) be a connected graph, \(n\) the order of \(G\), and \(f\) (resp. \(t\)) the maximum order of an induced forest (resp. tree) in \(G\). ...

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...

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 ...

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...

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...

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...

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>. ...

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...

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...

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...

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...

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 ...

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...

In this paper we present a simple technique that uses background information to improve mining the frequent patterns of structured data. This technique uses ...

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...

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...

<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...

This paper proposes to use local search inside filtering algorithms of combinatorial structures for which achieving a desired level of consistency is too c...

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 ...

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...

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...

We consider the bandwidth coloring problem, a generalization of the well-known graph coloring problem. For the latter problem, a classical theorem, discover...

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...

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...

In this paper, we propose efficient algorithms to extract minimal unsatisfiable subsets of clauses or variables in unsatisfiable propositional formulas. Suc...

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...

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,.....

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...

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...

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 ...

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...

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...

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"...

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...

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 ...

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 ...

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...

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...

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...

The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard probl...

<i>Tabucol</i>&nbsp; is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a &#64257;xed number <i>k</...

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 ...

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 ...

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...

Given a finite set <i>E</i> and a family <i>F</i>={<i>E</i>₁,...,<i>E_m</i>} of subsets of <i>E</i> such that <i>F</i> covers <i>E</i>...

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 ...

The 18^th EURO Summer/Winter Institute (ESWI XVIII) took place during the spring 2000 in Switzerland. The topic of ESWI XVIII, "Meta-heuristics in ...

Arc routing problems (ARPs) arise naturally in several applications where streets require maintenance, or customers located along road must be serviced. The ...

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...

The complexity status of the maximum stable set problem in the class of <i>P</i>₅-free graphs is unknown. In this paper, we first propose a chara...

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 ...

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...

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 ...

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...

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...

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...

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...

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...

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...

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'<...

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> ...

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...

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...

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...

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 ...

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...