Marc Demange

Publication Activity (10 Years)

Years Active: 1994-2024
Publications (10 Years): 23

Top Topics

Agnostic Learning

Hard Optimization Problems

Top Venues

Theor. Comput. Sci.

Publications

Marc Demange, Marcel Adonis Haddad, Cécile Murat
Approximating the probabilistic p-Center problem under pressure. J. Comb. Optim. 48 (1) (2024)
Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini
About the Infinite Windy Firebreak Location problem. CoRR (2022)
Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini
A graph theoretical approach to the firebreak locating problem. Theor. Comput. Sci. 914 (2022)
Marc Demange, David Ellison, Bertrand Jouve
Orienteering problem with time-windows and updating delay. CoRR (2022)
Marc Demange, Martin Olsen
Generalised online colouring problems in overlap graphs. Theor. Comput. Sci. 877 (2021)
Marc Demange, David Ellison, Bertrand Jouve
Orienteering problem with time-windows and updating delay. Theor. Comput. Sci. 863 (2021)
Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini
A graph theoretical approach to the firebreak locating problem. CoRR (2021)
Marc Demange, Virginie Gabrel, Marcel Adonis Haddad, Cécile Murat
-Center problem under pressure to locate shelters in wildfire context. EURO J. Comput. Optim. 8 (2) (2020)
Marc Demange, Marcel Adonis Haddad, Cécile Murat
Hardness and approximation of the Probabilistic p-Center problem under Pressure. CoRR (2020)
Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve
Firefighting on trees. Theor. Comput. Sci. 794 (2019)
Marc Demange, David Ellison, Raffaella Gentilini
Online Firefighting on Grids. ICTCS (2019)
Marc Demange, David Ellison, Raffaella Gentilini
Online Firefighting on Grids. CoRR (2019)
Ferhat Alkan, Türker Bíyíkoglu, Marc Demange, Cesim Erten
Structure of conflict graphs in constraint alignment problems and algorithms. Discret. Math. Theor. Comput. Sci. 21 (4) (2019)
Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve
Firefighting on Trees. CoRR (2019)
Marc Demange, Marcel Adonis Haddad, Cécile Murat
The probabilistic k-center problem. RSFF (2018)
Marc Demange, Martin Olsen
A Note on Online Colouring Problems in Overlap Graphs and Their Complements. WALCOM (2018)
Adan Rodríguez, Begoña Vitoriano, Marc Demange, Ignacio Leguey
Locating fuel breaks to minimise the risk of impact of wild fire. RSFF (2018)
Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve
Online Firefighting on Trees. ISCO (2018)
Paniz Abedin, Saieed Akbari, Marc Demange, Tínaz Ekim
Complexity of the Improper Twin Edge Coloring of Graphs. Graphs Comb. 33 (4) (2017)
Marc Demange, Cerasela Tanasescu
A Multi-period Vertex Cover Problem and Application to Fuel Management. ICORES (2016)
Marc Demange, Dominique de Werra
Choosability with limited number of colors. CoRR (2016)
Marc Demange, Tínaz Ekim, Bernard Ries
On the minimum and maximum selective graph coloring problems in some graph classes. Discret. Appl. Math. 204 (2016)
Paniz Abedin, Saieed Akbari, Mahsa Daneshmand, Marc Demange, Tínaz Ekim
Improper Twin Edge Coloring of Graphs. CoRR (2016)
Marc Demange, Tínaz Ekim, Bernard Ries, Cerasela Tanasescu
On some applications of the selective graph coloring problem. Eur. J. Oper. Res. 240 (2) (2015)
Marc Demange, Tínaz Ekim, Bernard Ries
On the Minimum and Maximum Selective Graph Coloring Problems. CTW (2015)
Yerim Chung, Jean-François Culus, Marc Demange
Inverse chromatic number problems in interval and permutation graphs. Eur. J. Oper. Res. 243 (3) (2015)
Marc Demange
Online Strategies for Hard Optimization Problems in Graphs. ICORES (2015)
Jean-François Culus, Marc Demange, Ruxandra Marinescu-Ghemeci, Cerasela Tanasescu
About some robustness and complexity properties of G-graphs networks. Discret. Appl. Math. 182 (2015)
Marc Demange, Tínaz Ekim
Efficient recognition of equimatchable graphs. Inf. Process. Lett. 114 (1-2) (2014)
Ferhat Alkan, Türker Bíyíkoglu, Marc Demange, Cesim Erten
Constrained Alignments of a Pair of Graphs. CoRR (2014)
Marc Demange, Tínaz Ekim, Cerasela Tanasescu
Hardness and approximation of minimum maximal matchings. Int. J. Comput. Math. 91 (8) (2014)
Marc Demange, Jérôme Monnot, Petrica C. Pop, Bernard Ries
On the complexity of the selective graph coloring problem in some special classes of graphs. Theor. Comput. Sci. 540 (2014)
Konrad K. Dabrowski, Marc Demange, Vadim V. Lozin
New results on maximum induced matchings in bipartite graphs and beyond. Theor. Comput. Sci. 478 (2013)
Marc Demange, Tínaz Ekim
A note on the NP-hardness of two matching problems in induced subgrids. Discret. Math. Theor. Comput. Sci. 15 (2) (2013)
Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange, Vangelis Th. Paschos
Playing with Parameters: Cross-parameterization in Graphs. CoRR (2013)
Marc Demange, Vadim V. Lozin, Christophe Picouleau, Bernard Ries
GO VII Meeting, Ovronnaz (CH), June 13-17, 2010. Discret. Appl. Math. 161 (4-5) (2013)
Marc Demange, Dominique de Werra
On some coloring problems in grids. Theor. Comput. Sci. 472 (2013)
Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu
On the online track assignment problem. Discret. Appl. Math. 160 (7-8) (2012)
Marc Demange, Jérôme Monnot, Petrica C. Pop, Bernard Ries
Selective Graph Coloring in Some Special Classes of Graphs. ISCO (2012)
Yerim Chung, Marc Demange
On inverse traveling salesman problems. 4OR 10 (2) (2012)
Yerim Chung, Jean-François Culus, Marc Demange
On Inverse Chromatic Number problems (Extended abstract). Electron. Notes Discret. Math. 36 (2010)
Marc Demange, Tínaz Ekim, Dominique de Werra
A tutorial on the use of graph coloring for some problems in robotics. Eur. J. Oper. Res. 192 (1) (2009)
Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. Discret. Appl. Math. 157 (4) (2009)
Marc Demange, Tínaz Ekim
Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs. TAMC (2008)
Yerim Chung, Marc Demange
The 0-1 inverse maximum stable set problem. Discret. Appl. Math. 156 (13) (2008)
Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu
Online Bounded Coloring of Permutation and Overlap Graphs. Electron. Notes Discret. Math. 30 (2008)
Yerim Chung, Jean-François Culus, Marc Demange
Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs. WALCOM (2008)
Yerim Chung, Marc Demange
Some Inverse Traveling Salesman Problems. Electron. Notes Discret. Math. 30 (2008)
Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos
Time slot scheduling of compatible jobs. J. Sched. 10 (2) (2007)
Marc Demange, Tínaz Ekim, Dominique de Werra
On the approximation of Min Split-coloring and Min Cocoloring. J. Graph Algorithms Appl. 10 (2) (2006)
Jean-François Culus, Marc Demange
Oriented Coloring: Complexity and Approximation. SOFSEM (2006)
Marc Demange, Vangelis Th. Paschos
Improved Approximations for Weighted and Unweighted Graph Problems. Theory Comput. Syst. 38 (6) (2005)
Marc Demange, Bernard Kouakou, Éric Soutif
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems. ISAAC (2005)
Marc Demange, Tínaz Ekim, Dominique de Werra
(p, k)-coloring problems in line graphs. Electron. Notes Discret. Math. 19 (2005)
Marc Demange, Xavier Paradon, Vangelis Th. Paschos
On-line maximum-order induced hereditary subgraph problems. Int. Trans. Oper. Res. 12 (2) (2005)
Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
Completeness in differential approximation classes. Int. J. Found. Comput. Sci. 16 (6) (2005)
Marc Demange, Tínaz Ekim, Dominique de Werra
Partitioning cographs into cliques and stable sets. Discret. Optim. 2 (2) (2005)
Marc Demange, Tínaz Ekim, Dominique de Werra
)-coloring problems in line graphs. Theor. Comput. Sci. 349 (3) (2005)
Marc Demange, Vangelis Th. Paschos
On-line vertex-covering. Theor. Comput. Sci. 332 (1-3) (2005)
Marc Demange, Vangelis Th. Paschos
Polynomial approximation algorithms with performance guarantees: An introduction-by-example. Eur. J. Oper. Res. 165 (3) (2005)
Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
A hypocoloring model for batch scheduling. Discret. Appl. Math. 146 (1) (2005)
Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos
Algorithms for the On-Line Quota Traveling Salesman Problem. Inf. Process. Lett. 92 (2) (2004)
Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos
Algorithms for the On-Line Quota Traveling Salesman Problem. COCOON (2004)
Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small. WG (2004)
Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier
Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation. ISAAC (2004)
Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
Differential approximation results for the Steiner tree problem. Appl. Math. Lett. 16 (5) (2003)
Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
Completeness in Differential Approximation Classes. MFCS (2003)
Marc Demange, Vangelis Th. Paschos
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation. RAIRO Oper. Res. 36 (3) (2002)
Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos
Weighted Node Coloring: When Stable Sets Are Expensive. WG (2002)
Marc Demange, Vangelis Th. Paschos
Algorithms and Models for the On-Line Vertex-Covering. WG (2002)
Marc Demange, Vangelis Th. Paschos
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances. RAIRO Oper. Res. 36 (4) (2002)
Marc Demange, Xavier Paradon, Vangelis Th. Paschos
On-Line Maximum-Order Induces Hereditary Subgraph Problems. SOFSEM (2000)
Marc Demange, Vangelis Th. Paschos
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems. RAIRO Oper. Res. 33 (4) (1999)
Marc Demange
A Note on the Approximation of a Minimum-Weight Maximal Independent Set. Comput. Optim. Appl. 14 (1) (1999)
Marc Demange, Pascal Grisoni, Vangelis Th. Paschos
Differential Approximation Algorithms for Some Combinatorial Optimization Problems. Theor. Comput. Sci. 209 (1-2) (1998)
Marc Demange, Vangelis Th. Paschos
The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems. Comput. Optim. Appl. 7 (3) (1997)
Marc Demange, Vangelis Th. Paschos
On an Approximation Measure Founded on the Links Between Optimization and Polynomial Approximation Theory. Theor. Comput. Sci. 158 (1&2) (1996)
Marc Demange, Vangelis Th. Paschos
Constructive - Non-constructive Approximation and Maximum Independent Set Problem. Combinatorics and Computer Science (1995)
Marc Demange, Pascal Grisoni, Vangelis Th. Paschos
Approximation Results for the Minimum Graph Coloring Problem. Inf. Process. Lett. 50 (1) (1994)