×

zbMATH — the first resource for mathematics

Demange, Marc

Compute Distance To:
Author ID: demange.marc Recent zbMATH articles by "Demange, Marc"
Published as: Demange, Marc; Demange, M.; DeMange, Marc; Demange, Mare; Demage, Marc
Documents Indexed: 77 Publications since 1993, including 1 Book

Publications by Year

Citations contained in zbMATH Open

54 Publications have been cited 356 times in 225 Documents Cited by Year
On an approximation measure founded on the links between optimization and polynomial approximation theory. Zbl 0871.90069
Demange, Marc; Paschos, Vangelis Th
36
1996
Differential approximation algorithms for some combinatorial optimization problems. Zbl 0912.68061
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
23
1998
Weighted node coloring: When stable sets are expensive. Zbl 1022.68092
Demange, Marc; de Werra, D.; Monnot, J.; Paschos, Vangelis Th.
17
2002
Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. Zbl 1173.05325
de Werra, D.; Demange, M.; Escoffier, B.; Monnot, J.; Paschos, V. Th.
16
2009
New results on maximum induced matchings in bipartite graphs and beyond. Zbl 1267.68118
Dabrowski, Konrad K.; Demange, Marc; Lozin, Vadim V.
16
2013
Partitioning cographs into cliques and stable sets. Zbl 1136.05315
Demange, Marc; Ekim, Tınaz; de Werra, Dominique
15
2005
Time slot scheduling of compatible jobs. Zbl 1154.90439
Demange, M.; de Werra, D.; Monnot, J.; Paschos, V. Th.
15
2007
Algorithms for the on-line quota traveling salesman problem. Zbl 1178.90282
Ausiello, G.; Demange, M.; Laura, L.; Paschos, V.
14
2004
On some applications of the selective graph coloring problem. Zbl 1357.05041
Demange, Marc; Ekim, Tınaz; Ries, Bernard; Tanasescu, Cerasela
14
2015
Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Zbl 0942.68144
Demange, M.; Monnot, J.; Paschos, V. Th.
11
1999
Approximation results for the minimum graph coloring problem. Zbl 0806.68085
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
10
1994
On-line vertex-covering. Zbl 1070.68118
Demange, Marc; Paschos, Vangelis Th.
9
2005
On the complexity of the selective graph coloring problem in some special classes of graphs. Zbl 1418.68102
Demange, Marc; Monnot, Jérôme; Pop, Petrica; Ries, Bernard
9
2014
An introduction to inverse combinatorial problems. Zbl 1229.90157
Demange, Marc; Monnot, Jérôme
9
2010
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios. Zbl 0919.90140
Paschos, Vangelis Th.; Demange, Marc
9
1997
A tutorial on the use of graph coloring for some problems in robotics. Zbl 1198.05045
Demange, Marc; Ekim, Tınaz; De Werra, Dominique
8
2009
Minimum maximal matching is NP-hard in regular bipartite graphs. Zbl 1139.05337
Demange, M.; Ekim, T.
7
2008
The 0-1 inverse maximum stable set problem. Zbl 1152.68039
Chung, Yerim; Demange, Marc
7
2008
Improved approximations for maximum independent set via approximation chains. Zbl 0883.68067
Demange, M.; Paschos, V. Th.
7
1997
Maximizing the number of unused bins. Zbl 1204.90080
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis Th.
6
2001
A hypocoloring model for batch scheduling. Zbl 1115.68118
de Werra, D.; Demange, M.; Monnot, J.; Paschos, V. Th.
6
2005
Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation. Zbl 1116.68565
de Werra, Dominique; Demange, Mare; Escoffier, Bruno; Monnot, Jerome; Paschos, Vangelis Th.
6
2004
Completeness in differential approximation classes. Zbl 1124.68365
Ausiello, G.; Bazgan, C.; Demange, M.; Paschos, V. Th.
6
2003
Oriented coloring: complexity and approximation. Zbl 1175.05054
Culus, Jean-François; Demange, Marc
6
2006
Efficient recognition of equimatchable graphs. Zbl 1329.05243
Demange, Marc; Ekim, Tınaz
5
2014
On-line maximum-order induced hereditary subgraph problems. Zbl 1043.68615
Demange, Marc; Paradon, Xavier; Paschos, Vangelis Th.
5
2000
On inverse traveling salesman problems. Zbl 1261.90041
Chung, Yerim; Demange, Marc
4
2012
\((p,k)\)-coloring problems in line graphs. Zbl 1086.05029
Demange, Marc; Ekim, Tınaz; de Werra, Dominique
4
2005
On the minimum and maximum selective graph coloring problems in some graph classes. Zbl 1333.05106
Demange, Marc; Ekim, Tınaz; Ries, Bernard
4
2016
Improved approximations for weighted and unweighted graph problems. Zbl 1085.68105
Demange, Marc; Paschos, Vangelis
4
2005
On the online track assignment problem. Zbl 1238.90088
Demange, Marc; Di Stefano, Gabriele; Leroy-Beaulieu, Benjamin
3
2012
Selective graph coloring in some special classes of graphs. Zbl 1370.05167
Demange, Marc; Monnot, Jérôme; Pop, Petrica; Ries, Bernard
3
2012
On some coloring problems in grids. Zbl 1257.68071
Demange, Marc; De Werra, Dominique
3
2013
Some steps towards the conciliation of approximation and optimization theory: a new suggested approximation measure and preliminary results. (Quelques étapes vers la conciliation de la théorie d’approximation et celle d’optimisation: une nouvelle théorie d’approximation polynomiale et résultats préliminaires.) Zbl 0785.90074
Demange, Marc; Paschos, Vangelis Th.
3
1993
On inverse chromatic number problems (extended abstract). Zbl 1274.05152
Chung, Yerim; Culus, Jean-François; Demange, Marc
3
2010
Inverse booking problem: Inverse chromatic number problem in interval graphs. Zbl 1132.90372
Chung, Yerim; Culus, Jean-François; Demange, Marc
3
2008
On the approximation of min split-coloring and min cocoloring. Zbl 1161.68652
Demange, Marc; Ekim, Tinaz; De Werra, Dominique
3
2006
Completeness in differential approximation classes. Zbl 1081.68121
Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis Th.
3
2005
A note on the approximation of a minimum-weight maximal independent set. Zbl 0958.90093
Demange, Marc
3
1999
Polynomial approximation algorithms with performance guarantees: an introduction-by-example. Zbl 1062.90053
Demange, Marc; Paschos, Vangelis Th.
2
2005
On-line maximum-order induced hereditary subgraph problems. Zbl 1063.90059
Demange, Marc; Paradon, Xavier; Paschos, Vangelis Th.
2
2005
A note on the NP-hardness of two matching problems in induced subgrids. Zbl 1281.68122
Demange, Marc; Ekim, Tınaz
2
2013
Hardness and approximation of minimum maximal matchings. Zbl 1305.05188
Demange, Marc; Ekim, Tınaz; Tanasescu, Cerasela
2
2014
On new notions for the analysis of approximation algorithms: a unified formalism and approximation classes. (Autour de nouvelles notions pour l’analyse des algorithmes d’approximation: formalisme unifié et classes d’approximation.) Zbl 1089.68668
Demage, Marc; Paschos, Vangelis
2
2002
Extremal values of a combinatorial optimization problem and polynomial approximation. (Valeurs extrémales d’un problème d’optimisation combinatoire et approximation polynomiale.) Zbl 0885.90093
Demange, Marc; Paschos, Vangelis Th.
2
1996
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems. Zbl 0872.90106
DeMange, Marc; Paschos, Vangelis Th.
1
1997
Some results in the frame of a new polynomial approximation theory. (Quelques résultats dans le cadre d’une nouvelle théorie de l’approximation polynomiale.) Zbl 0793.41011
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
1
1994
Some inverse traveling salesman problems. Zbl 1278.90332
Chung, Yerim; Demange, Marc
1
2008
Online bounded coloring of permutation and overlap graphs. Zbl 1341.05069
Demange, Marc; Di Stefano, Gabriele; Leroy-Beaulieu, Benjamin
1
2008
About some robustness and complexity properties of \(G\)-graphs networks. Zbl 1306.05230
Culus, Jean-François; Demange, Marc; Marinescu-Ghemeci, Ruxandra; Tanasescu, Cerasela
1
2015
Inverse chromatic number problems in interval and permutation graphs. Zbl 1346.05062
Chung, Yerim; Culus, Jean-François; Demange, Marc
1
2015
About new notions for the analysis of approximation algorithms: from the NPO structure to the structure of instants. (Autour de nouvelles notions pour l’analyse des algorithmes d’approximation: De la structure de NPO à la structure des instances.) Zbl 1096.68783
Demange, Marc; Paschos, Vangelis
1
2002
Differential approximation results for the Steiner tree problem. Zbl 1046.90096
Demange, M.; Monnot, J.; Paschos, V. Th
1
2003
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems. Zbl 0961.90084
Demange, Marc; Paschos, Vangelis Th.
1
1999
On the minimum and maximum selective graph coloring problems in some graph classes. Zbl 1333.05106
Demange, Marc; Ekim, Tınaz; Ries, Bernard
4
2016
On some applications of the selective graph coloring problem. Zbl 1357.05041
Demange, Marc; Ekim, Tınaz; Ries, Bernard; Tanasescu, Cerasela
14
2015
About some robustness and complexity properties of \(G\)-graphs networks. Zbl 1306.05230
Culus, Jean-François; Demange, Marc; Marinescu-Ghemeci, Ruxandra; Tanasescu, Cerasela
1
2015
Inverse chromatic number problems in interval and permutation graphs. Zbl 1346.05062
Chung, Yerim; Culus, Jean-François; Demange, Marc
1
2015
On the complexity of the selective graph coloring problem in some special classes of graphs. Zbl 1418.68102
Demange, Marc; Monnot, Jérôme; Pop, Petrica; Ries, Bernard
9
2014
Efficient recognition of equimatchable graphs. Zbl 1329.05243
Demange, Marc; Ekim, Tınaz
5
2014
Hardness and approximation of minimum maximal matchings. Zbl 1305.05188
Demange, Marc; Ekim, Tınaz; Tanasescu, Cerasela
2
2014
New results on maximum induced matchings in bipartite graphs and beyond. Zbl 1267.68118
Dabrowski, Konrad K.; Demange, Marc; Lozin, Vadim V.
16
2013
On some coloring problems in grids. Zbl 1257.68071
Demange, Marc; De Werra, Dominique
3
2013
A note on the NP-hardness of two matching problems in induced subgrids. Zbl 1281.68122
Demange, Marc; Ekim, Tınaz
2
2013
On inverse traveling salesman problems. Zbl 1261.90041
Chung, Yerim; Demange, Marc
4
2012
On the online track assignment problem. Zbl 1238.90088
Demange, Marc; Di Stefano, Gabriele; Leroy-Beaulieu, Benjamin
3
2012
Selective graph coloring in some special classes of graphs. Zbl 1370.05167
Demange, Marc; Monnot, Jérôme; Pop, Petrica; Ries, Bernard
3
2012
An introduction to inverse combinatorial problems. Zbl 1229.90157
Demange, Marc; Monnot, Jérôme
9
2010
On inverse chromatic number problems (extended abstract). Zbl 1274.05152
Chung, Yerim; Culus, Jean-François; Demange, Marc
3
2010
Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. Zbl 1173.05325
de Werra, D.; Demange, M.; Escoffier, B.; Monnot, J.; Paschos, V. Th.
16
2009
A tutorial on the use of graph coloring for some problems in robotics. Zbl 1198.05045
Demange, Marc; Ekim, Tınaz; De Werra, Dominique
8
2009
Minimum maximal matching is NP-hard in regular bipartite graphs. Zbl 1139.05337
Demange, M.; Ekim, T.
7
2008
The 0-1 inverse maximum stable set problem. Zbl 1152.68039
Chung, Yerim; Demange, Marc
7
2008
Inverse booking problem: Inverse chromatic number problem in interval graphs. Zbl 1132.90372
Chung, Yerim; Culus, Jean-François; Demange, Marc
3
2008
Some inverse traveling salesman problems. Zbl 1278.90332
Chung, Yerim; Demange, Marc
1
2008
Online bounded coloring of permutation and overlap graphs. Zbl 1341.05069
Demange, Marc; Di Stefano, Gabriele; Leroy-Beaulieu, Benjamin
1
2008
Time slot scheduling of compatible jobs. Zbl 1154.90439
Demange, M.; de Werra, D.; Monnot, J.; Paschos, V. Th.
15
2007
Oriented coloring: complexity and approximation. Zbl 1175.05054
Culus, Jean-François; Demange, Marc
6
2006
On the approximation of min split-coloring and min cocoloring. Zbl 1161.68652
Demange, Marc; Ekim, Tinaz; De Werra, Dominique
3
2006
Partitioning cographs into cliques and stable sets. Zbl 1136.05315
Demange, Marc; Ekim, Tınaz; de Werra, Dominique
15
2005
On-line vertex-covering. Zbl 1070.68118
Demange, Marc; Paschos, Vangelis Th.
9
2005
A hypocoloring model for batch scheduling. Zbl 1115.68118
de Werra, D.; Demange, M.; Monnot, J.; Paschos, V. Th.
6
2005
\((p,k)\)-coloring problems in line graphs. Zbl 1086.05029
Demange, Marc; Ekim, Tınaz; de Werra, Dominique
4
2005
Improved approximations for weighted and unweighted graph problems. Zbl 1085.68105
Demange, Marc; Paschos, Vangelis
4
2005
Completeness in differential approximation classes. Zbl 1081.68121
Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis Th.
3
2005
Polynomial approximation algorithms with performance guarantees: an introduction-by-example. Zbl 1062.90053
Demange, Marc; Paschos, Vangelis Th.
2
2005
On-line maximum-order induced hereditary subgraph problems. Zbl 1063.90059
Demange, Marc; Paradon, Xavier; Paschos, Vangelis Th.
2
2005
Algorithms for the on-line quota traveling salesman problem. Zbl 1178.90282
Ausiello, G.; Demange, M.; Laura, L.; Paschos, V.
14
2004
Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation. Zbl 1116.68565
de Werra, Dominique; Demange, Mare; Escoffier, Bruno; Monnot, Jerome; Paschos, Vangelis Th.
6
2004
Completeness in differential approximation classes. Zbl 1124.68365
Ausiello, G.; Bazgan, C.; Demange, M.; Paschos, V. Th.
6
2003
Differential approximation results for the Steiner tree problem. Zbl 1046.90096
Demange, M.; Monnot, J.; Paschos, V. Th
1
2003
Weighted node coloring: When stable sets are expensive. Zbl 1022.68092
Demange, Marc; de Werra, D.; Monnot, J.; Paschos, Vangelis Th.
17
2002
On new notions for the analysis of approximation algorithms: a unified formalism and approximation classes. (Autour de nouvelles notions pour l’analyse des algorithmes d’approximation: formalisme unifié et classes d’approximation.) Zbl 1089.68668
Demage, Marc; Paschos, Vangelis
2
2002
About new notions for the analysis of approximation algorithms: from the NPO structure to the structure of instants. (Autour de nouvelles notions pour l’analyse des algorithmes d’approximation: De la structure de NPO à la structure des instances.) Zbl 1096.68783
Demange, Marc; Paschos, Vangelis
1
2002
Maximizing the number of unused bins. Zbl 1204.90080
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis Th.
6
2001
On-line maximum-order induced hereditary subgraph problems. Zbl 1043.68615
Demange, Marc; Paradon, Xavier; Paschos, Vangelis Th.
5
2000
Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Zbl 0942.68144
Demange, M.; Monnot, J.; Paschos, V. Th.
11
1999
A note on the approximation of a minimum-weight maximal independent set. Zbl 0958.90093
Demange, Marc
3
1999
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems. Zbl 0961.90084
Demange, Marc; Paschos, Vangelis Th.
1
1999
Differential approximation algorithms for some combinatorial optimization problems. Zbl 0912.68061
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
23
1998
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios. Zbl 0919.90140
Paschos, Vangelis Th.; Demange, Marc
9
1997
Improved approximations for maximum independent set via approximation chains. Zbl 0883.68067
Demange, M.; Paschos, V. Th.
7
1997
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems. Zbl 0872.90106
DeMange, Marc; Paschos, Vangelis Th.
1
1997
On an approximation measure founded on the links between optimization and polynomial approximation theory. Zbl 0871.90069
Demange, Marc; Paschos, Vangelis Th
36
1996
Extremal values of a combinatorial optimization problem and polynomial approximation. (Valeurs extrémales d’un problème d’optimisation combinatoire et approximation polynomiale.) Zbl 0885.90093
Demange, Marc; Paschos, Vangelis Th.
2
1996
Approximation results for the minimum graph coloring problem. Zbl 0806.68085
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
10
1994
Some results in the frame of a new polynomial approximation theory. (Quelques résultats dans le cadre d’une nouvelle théorie de l’approximation polynomiale.) Zbl 0793.41011
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis Th.
1
1994
Some steps towards the conciliation of approximation and optimization theory: a new suggested approximation measure and preliminary results. (Quelques étapes vers la conciliation de la théorie d’approximation et celle d’optimisation: une nouvelle théorie d’approximation polynomiale et résultats préliminaires.) Zbl 0785.90074
Demange, Marc; Paschos, Vangelis Th.
3
1993
all top 5

Cited by 352 Authors

33 Paschos, Vangelis Th.
26 Demange, Marc
20 Ekim, Tınaz
18 Monnot, Jérôme
12 Escoffier, Bruno
10 de Werra, Dominique
9 Levit, Vadim E.
8 Mandrescu, Eugen
8 Rautenbach, Dieter
7 Bazgan, Cristina
5 Ausiello, Giorgio
5 Chung, Yerim
5 Joos, Felix Claudius
5 Lucarelli, Giorgio
5 Malaguti, Enrico
5 Milis, Ioannis
5 Ries, Bernard
4 Bourgeois, Nicolas
4 Fürst, Maximilian
4 Klein, Sulamita
4 Shalom, Mordechai
4 Sirdey, Renaud
4 Taşkın, Z. Caner
4 Toulouse, Sophie
3 Baste, Julien
3 Bonifaci, Vincenzo
3 Carlier, Jacques G.
3 Cornaz, Denis
3 Furini, Fabio
3 Hassin, Refael
3 Laura, Luigi
3 Murat, Cécile
3 Nace, Dritan
3 Pop, Petrică Claudiu
3 Strusevich, Vitaly A.
2 Abu-Khzam, Faisal N.
2 Araújo, Júlio César Silva
2 Bonomo, Flavia
2 Boudhar, Mourad
2 Boyar, Joan F.
2 Boysen, Nils
2 Bravo, Raquel S. F.
2 Campos, Victor A.
2 Culus, Jean-François
2 Dabrowski, Konrad Kazimierz
2 Delbot, François
2 Deniz, Zakir
2 Di Stefano, Gabriele
2 Draque Penso, Lucia
2 Duarte, Marcio Antônio
2 Ellison, David J.
2 Emde, Simon
2 Epple, Dennis D. A.
2 Epstein, Leah
2 Faria, Luerbio
2 Ferber, Aaron
2 Fernau, Henning
2 Freund, Daniel
2 Gözüpek, Didem
2 Halldórsson, Magnús Mar
2 Huang, Jing
2 Jost, Vincent
2 Kerivin, Hervé L. M.
2 Knust, Sigrid
2 Kudahl, Christian
2 Laforest, Christian
2 Lai, Hong-Jian
2 Langerman, Stefan
2 Li, Shuangshuang
2 Lin, Min Chih
2 Lozin, Vadim Vladislavovich
2 Mahadev, N. V. R.
2 Nogueira, Loana Tito
2 Nonner, Tim
2 Ochem, Pascal
2 Orlovich, Yury L.
2 Paul, Alice
2 Protti, Fábio
2 Punnen, Abraham P.
2 Sampaio, Rudini Menezes
2 Santini, Alberto
2 Sau, Ignasi
2 Şeker, Oylum
2 Shakhlevich, Natalia V.
2 Shmoys, David B.
2 Sopena, Éric
2 Souza, Uéverton S.
2 Tayyebi, Javad
2 Toth, Paolo
2 Waldherr, Stefan
2 Williamson, David P.
2 Zenklusen, Rico
2 Zhang, Zhao
1 Abdolhosseinzadeh, Mohsen
1 Adefokun, Tayo Charles
1 Afif, Mohamed
1 Ahat, Betül
1 Ajayi, Deborah Olayide A.
1 Akbari, Saieed
1 Akdemir, Ahu
...and 252 more Authors
all top 5

Cited in 53 Serials

33 Discrete Applied Mathematics
27 Theoretical Computer Science
20 European Journal of Operational Research
15 Information Processing Letters
10 Discrete Mathematics
9 RAIRO. Operations Research
8 Journal of Combinatorial Optimization
7 Discrete Optimization
4 Operations Research Letters
4 Graphs and Combinatorics
4 Annals of Operations Research
4 Theory of Computing Systems
4 Journal of Discrete Algorithms
3 Journal of Graph Theory
3 Algorithmica
3 Computers & Operations Research
3 SIAM Journal on Discrete Mathematics
3 Journal of Heuristics
3 Optimization Letters
2 Networks
2 Applied Mathematics Letters
2 Journal of Global Optimization
2 International Transactions in Operational Research
2 Soft Computing
2 4OR
2 Discrete Mathematics, Algorithms and Applications
2 Computer Science Review
1 Chaos, Solitons and Fractals
1 Information Sciences
1 Journal of Computational and Applied Mathematics
1 Journal of Computer and System Sciences
1 Journal of Optimization Theory and Applications
1 Mathematics of Operations Research
1 European Journal of Combinatorics
1 Acta Mathematicae Applicatae Sinica. English Series
1 International Journal of Foundations of Computer Science
1 Discrete Mathematics and Applications
1 International Journal of Computer Mathematics
1 Acta Universitatis Matthiae Belii. Series Mathematics
1 Constraints
1 INFORMS Journal on Computing
1 Mathematical Problems in Engineering
1 Optimization Methods & Software
1 Mathematical Methods of Operations Research
1 Journal of Scheduling
1 RAIRO. Theoretical Informatics and Applications
1 Journal of Systems Science and Complexity
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 International Journal of Intelligent Computing and Cybernetics
1 Ars Mathematica Contemporanea
1 Algorithms
1 EURO Journal on Computational Optimization
1 Journal of Mathematical Modeling

Citations by Year