Source author record

Marc Demange

Marc Demange appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

About the Infinite Windy Firebreak Location problem

The severity of wildfires can be mitigated adopting preventive measures like the construction of firebreaks that are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location. A land of unknown extension is modeled as an infinite undirected graph in which the vertices correspond to areas subject to fire and edges represent the propagation of fire from an area to another. The construction of a firebreak on the territory is modeled as the removal of edges in both directions between two vertices. The number of firebreaks that can be installed depends on budget constraints. We assume that fire ignites in a subset of vertices and propagates to the neighbours. The goal is to select a subset of edges to remove in order to contain the fire and avoid burning an infinite part of the graph. We prove that Infinite Windy Firebreak Location is coNP-complete in restricted cases and we address some polynomial cases. We show that Infinite Windy Firebreak Location polynomially reduces to Min Cut for certain classes of graphs like infinite grid graphs and polyomino-grids.

preprint2022arXiv

Orienteering problem with time-windows and updating delay

The Orienteering Problem with Time Window and Delay (\OPTiWinD) is a variant of the online orienteering problem. A series of requests appear in various locations while a vehicle moves within the territory to serve them. Each request has a time window during which it can be served and a weight which describes its importance. There is also a minimum delay $T$ between successive requests. The objective is to find a path for the vehicles that maximises the sum of the weights of the requests served. We further assume that the length of each time window is equal to the diameter of the territory. We study the optimal performance and competitive ratio for the set of instances with $n$ requests. We obtain complete resolution for $T$ at least half of the diameter, small values of $T$ or small values of $n$, as well as partial results in the remaining cases.

preprint2016arXiv

Improper Twin Edge Coloring of Graphs

Let $G$ be a graph whose each component has order at least 3. Let $s : E(G) \rightarrow \mathbb{Z}_k$ for some integer $k\geq 2$ be an improper edge coloring of $G$ (where adjacent edges may be assigned the same color). If the induced vertex coloring $c : V (G) \rightarrow \mathbb{Z}_k$ defined by $c(v) = \sum_{e\in E_v} s(e) \mbox{ in } \mathbb{Z}_k,$ (where the indicated sum is computed in $\mathbb{Z}_k$ and $E_v$ denotes the set of all edges incident to $v$) results in a proper vertex coloring of $G$, then we refer to such a coloring as an improper twin $k$-edge coloring. The minimum $k$ for which $G$ has an improper twin $k$-edge coloring is called the improper twin chromatic index of $G$ and is denoted by $χ'_{it}(G)$. In this paper, we show that if $G$ is a graph with vertex chromatic number $χ(G)$, then $χ'_{it}(G)=χ(G)$, unless $χ(G)=2 \pmod 4$ and in this case $χ'_{it}(G)\in \{χ(G), χ(G)+1\}$. Moreover, we show that it is NP-hard to decide whether $χ'_{it}(G)=χ(G)$ or $χ'_{it}(G)=χ(G)+1$ and give some examples of perfect graph classes for which the problem is polynomial.

preprint2013arXiv

Playing with parameters: structural parameterization in graphs

When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem (the "standard" parameter). A natural subject for investigation is what happens when we parameterize such a problem by various other parameters, some of which may be the values of optimal solutions to different problems. Such research is known as parameterized ecology. In this paper, we investigate seven natural vertex problems, along with their respective parameters: the size of a maximum independent set, the size of a minimum vertex cover, the size of a maximum clique, the chromatic number, the size of a minimum dominating set, the size of a minimum independent dominating set and the size of a minimum feedback vertex set. We study the parameterized complexity of each of these problems with respect to the standard parameter of the others.