Marc Demange

According to our database, Marc Demange authored at least 73 papers between 1994 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Approximating the probabilistic p-Center problem under pressure.

Marc Demange, Marcel Adonis Haddad, Cécile Murat

J. Comb. Optim., August, 2024

2022

A graph theoretical approach to the firebreak locating problem.

Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini

Theor. Comput. Sci., 2022

About the Infinite Windy Firebreak Location problem.

Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini

CoRR, 2022

2021

Generalised online colouring problems in overlap graphs.

Marc Demange, Martin Olsen

Theor. Comput. Sci., 2021

Orienteering problem with time-windows and updating delay.

Marc Demange, David Ellison, Bertrand Jouve

Theor. Comput. Sci., 2021

2020

A robust <i>p</i>-Center problem under pressure to locate shelters in wildfire context.

Marc Demange, Virginie Gabrel, Marcel Adonis Haddad, Cécile Murat

EURO J. Comput. Optim., 2020

Hardness and approximation of the Probabilistic p-Center problem under Pressure.

Marc Demange, Marcel Adonis Haddad, Cécile Murat

CoRR, 2020

2019

Firefighting on trees.

Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve

Theor. Comput. Sci., 2019

Structure of conflict graphs in constraint alignment problems and algorithms.

Ferhat Alkan, Türker Bíyíkoglu, Marc Demange, Cesim Erten

Discret. Math. Theor. Comput. Sci., 2019

Online Firefighting on Grids.

Marc Demange, David Ellison, Raffaella Gentilini

Proceedings of the 20th Italian Conference on Theoretical Computer Science, 2019

2018

A Note on Online Colouring Problems in Overlap Graphs and Their Complements.

Marc Demange, Martin Olsen

Proceedings of the WALCOM: Algorithms and Computation - 12th International Conference, 2018

Locating fuel breaks to minimise the risk of impact of wild fire.

Adan Rodríguez, Begoña Vitoriano, Marc Demange, Ignacio Leguey

Proceedings of the GEOSAFE Workshop on Robust Solutions for Fire Fighting, 2018

The probabilistic k-center problem.

Marc Demange, Marcel Adonis Haddad, Cécile Murat

Proceedings of the GEOSAFE Workshop on Robust Solutions for Fire Fighting, 2018

Online Firefighting on Trees.

Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

2017

Complexity of the Improper Twin Edge Coloring of Graphs.

Paniz Abedin, Saieed Akbari, Marc Demange, Tínaz Ekim

Graphs Comb., 2017

2016

On the minimum and maximum selective graph coloring problems in some graph classes.

Marc Demange, Tínaz Ekim, Bernard Ries

Discret. Appl. Math., 2016

Choosability with limited number of colors.

Marc Demange, Dominique de Werra

CoRR, 2016

Improper Twin Edge Coloring of Graphs.

Paniz Abedin, Saieed Akbari, Mahsa Daneshmand, Marc Demange, Tínaz Ekim

CoRR, 2016

A Multi-period Vertex Cover Problem and Application to Fuel Management.

Marc Demange, Cerasela Tanasescu

Proceedings of 5th the International Conference on Operations Research and Enterprise Systems (ICORES 2016), 2016

2015

On some applications of the selective graph coloring problem.

Marc Demange, Tínaz Ekim, Bernard Ries, Cerasela Tanasescu

Eur. J. Oper. Res., 2015

Inverse chromatic number problems in interval and permutation graphs.

Yerim Chung, Jean-François Culus, Marc Demange

Eur. J. Oper. Res., 2015

About some robustness and complexity properties of G-graphs networks.

Jean-François Culus, Marc Demange, Ruxandra Marinescu-Ghemeci, Cerasela Tanasescu

Discret. Appl. Math., 2015

Online Strategies for Hard Optimization Problems in Graphs.

Marc Demange

Proceedings of the ICORES 2015, 2015

On the Minimum and Maximum Selective Graph Coloring Problems.

Marc Demange, Tínaz Ekim, Bernard Ries

Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

2014

On the complexity of the selective graph coloring problem in some special classes of graphs.

Marc Demange, Jérôme Monnot, Petrica C. Pop, Bernard Ries

Theor. Comput. Sci., 2014

Efficient recognition of equimatchable graphs.

Marc Demange, Tínaz Ekim

Inf. Process. Lett., 2014

Hardness and approximation of minimum maximal matchings.

Marc Demange, Tínaz Ekim, Cerasela Tanasescu

Int. J. Comput. Math., 2014

Constrained Alignments of a Pair of Graphs.

Ferhat Alkan, Türker Bíyíkoglu, Marc Demange, Cesim Erten

CoRR, 2014

2013

On some coloring problems in grids.

Marc Demange, Dominique de Werra

Theor. Comput. Sci., 2013

New results on maximum induced matchings in bipartite graphs and beyond.

Konrad K. Dabrowski, Marc Demange, Vadim V. Lozin

Theor. Comput. Sci., 2013

A note on the NP-hardness of two matching problems in induced subgrids.

Marc Demange, Tínaz Ekim

Discret. Math. Theor. Comput. Sci., 2013

GO VII Meeting, Ovronnaz (CH), June 13-17, 2010.

Marc Demange, Vadim V. Lozin, Christophe Picouleau, Bernard Ries

Discret. Appl. Math., 2013

Playing with Parameters: Cross-parameterization in Graphs.

Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange, Vangelis Th. Paschos

CoRR, 2013

2012

On the online track assignment problem.

Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu

Discret. Appl. Math., 2012

On inverse traveling salesman problems.

Yerim Chung, Marc Demange

4OR, 2012

Selective Graph Coloring in Some Special Classes of Graphs.

Marc Demange, Jérôme Monnot, Petrica C. Pop, Bernard Ries

Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

2010

On Inverse Chromatic Number problems (Extended abstract).

Yerim Chung, Jean-François Culus, Marc Demange

Electron. Notes Discret. Math., 2010

2009

A tutorial on the use of graph coloring for some problems in robotics.

Marc Demange, Tínaz Ekim, Dominique de Werra

Eur. J. Oper. Res., 2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.

Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos

Discret. Appl. Math., 2009

2008

Online Bounded Coloring of Permutation and Overlap Graphs.

Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu

Electron. Notes Discret. Math., 2008

Some Inverse Traveling Salesman Problems.

Yerim Chung, Marc Demange

Electron. Notes Discret. Math., 2008

The 0-1 inverse maximum stable set problem.

Yerim Chung, Marc Demange

Discret. Appl. Math., 2008

Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs.

Yerim Chung, Jean-François Culus, Marc Demange

Proceedings of the WALCOM: Algorithms and Computation, Second International Workshop, 2008

Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs.

Marc Demange, Tínaz Ekim

Proceedings of the Theory and Applications of Models of Computation, 2008

2007

Time slot scheduling of compatible jobs.

Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos

J. Sched., 2007

2006

On the approximation of Min Split-coloring and Min Cocoloring.

Marc Demange, Tínaz Ekim, Dominique de Werra

J. Graph Algorithms Appl., 2006

Oriented Coloring: Complexity and Approximation.

Jean-François Culus, Marc Demange

Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

2005

On-line vertex-covering.

Marc Demange, Vangelis Th. Paschos

Theor. Comput. Sci., 2005

(<i>p</i>, <i>k</i>)-coloring problems in line graphs.

Marc Demange, Tínaz Ekim, Dominique de Werra

Theor. Comput. Sci., 2005

Improved Approximations for Weighted and Unweighted Graph Problems.

Marc Demange, Vangelis Th. Paschos

Theory Comput. Syst., 2005

On-line maximum-order induced hereditary subgraph problems.

Marc Demange, Xavier Paradon, Vangelis Th. Paschos

Int. Trans. Oper. Res., 2005

Completeness in differential approximation classes.

Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos

Int. J. Found. Comput. Sci., 2005

Polynomial approximation algorithms with performance guarantees: An introduction-by-example.

Marc Demange, Vangelis Th. Paschos

Eur. J. Oper. Res., 2005

(p, k)-coloring problems in line graphs.

Marc Demange, Tínaz Ekim, Dominique de Werra

Electron. Notes Discret. Math., 2005

Partitioning cographs into cliques and stable sets.

Marc Demange, Tínaz Ekim, Dominique de Werra

Discret. Optim., 2005

A hypocoloring model for batch scheduling.

Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Discret. Appl. Math., 2005

On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems.

Marc Demange, Bernard Kouakou, Éric Soutif

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

Algorithms for the On-Line Quota Traveling Salesman Problem.

Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos

Inf. Process. Lett., 2004

The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.

Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.

Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

Differential approximation results for the Steiner tree problem.

Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Appl. Math. Lett., 2003

2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 2002

Weighted Node Coloring: When Stable Sets Are Expensive.

Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Algorithms and Models for the On-Line Vertex-Covering.

Marc Demange, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

2000

On-Line Maximum-Order Induces Hereditary Subgraph Problems.

Marc Demange, Xavier Paradon, Vangelis Th. Paschos

Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

1999

Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 1999

A Note on the Approximation of a Minimum-Weight Maximal Independent Set.

Marc Demange

Comput. Optim. Appl., 1999

1998

Differential Approximation Algorithms for Some Combinatorial Optimization Problems.

Marc Demange, Pascal Grisoni, Vangelis Th. Paschos

Theor. Comput. Sci., 1998

1997

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems.

Marc Demange, Vangelis Th. Paschos

Comput. Optim. Appl., 1997

1996

On an Approximation Measure Founded on the Links Between Optimization and Polynomial Approximation Theory.

Marc Demange, Vangelis Th. Paschos

Theor. Comput. Sci., 1996

1995

Constructive - Non-constructive Approximation and Maximum Independent Set Problem.

Marc Demange, Vangelis Th. Paschos

Proceedings of the Combinatorics and Computer Science, 1995

1994

Approximation Results for the Minimum Graph Coloring Problem.

Marc Demange, Pascal Grisoni, Vangelis Th. Paschos

Inf. Process. Lett., 1994