Prof. Bernard Ries

Professor, head of group

T: +41 26 300 83 33

Address: Bd de Pérolles 90, 1700 Fribourg

Office: C 324

Email

 


 

Short bio

In 2007, I received my PhD in mathematics from Ecole Polytechnique Fédérale de Lausanne (CH). From 2008 to 2009, I was a Postdoctoral Research Fellow at Columbia University (US) in the Department of Industrial Engineering and Operations Research. In 2009-2010, I was appointed as Assistant Professor at the University of Warwick (UK) in the Center for Discrete Mathematics and its Applications (DIMAP) and the Warwick Business School (WBS). From September 2010 to July 2015, I was an Associate Professor at the Université Paris Dauphine (F) in the Computer Science and Mathematics Department. Currently I am a Professor at the University of Fribourg (CH), where I am heading the Decision Support & Operations Research Group together with Marino Widmer in the Department of Informatics.

My main research interests are:

  • Structural and algorithmic graph theory
  • Combinatorial optimization
  • Computational complexity
  • Mathematical Modeling

 

A detailed CV can be found here.


 

Teaching activities

 


 

Publications 

  • Submitted / to appear
    • Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width, E. Galby, A. Munaro, B. Ries, submitted (available on arxiv)

    • Classifying k-edge colouring for H-free graphs, E. Galby, P. T. Lima, D. Paulusma, B. Ries, submitted (available on arxiv)
    • On some special classes of contact B0-VPG graphs, F. Bonomo, M. P. Mazzoleni, M. L. Rean, B. Ries, submitted (available on arxiv)
    • Maximum Eccentric Connectivity Index for Graphs with given Diameter, P. Hauweele, A. Hertz, H. Mélot, B. Ries, G. Devillez, submitted (available on arxiv)
    • Detecting strong cliques, A. Hujdurovic, M. Milanic, B. Ries, submitted (available on arxiv)
    • Proper circular arc graphs as intersection graphs of paths in a grid, E. Galby, M.P. Mazzoleni, B. Ries, submitted (available on  arxiv)
    • On contact graphs of paths in  gridZ. Deniz, E. Galby, A. Munaro, B. Ries, to appear in Lecture Notes in Computer Science (Graph Drawing 2018) (available on  arxiv)
    • Critical Vertices and Edges in H-free Graphs, D. Paulusma, C. Picouleau, B. Ries, to appear in Discrete Applied Mathematics, doi

  • 2018
    • Upper domination: towards a dichotomy through boundary properties, H. AbouEisha, S. Hussain, V. Lozin, J. Monot, B. Ries, V. Zamaraev , Algorithmica 80(10) 2799-2817 (2018), doi
    • On split B1-EPG graphs, Z. Deniz, S. Nivelle, B. Ries, D. Schindl, Lecture Notes in Computer Science 10807, LATIN 2018, 361--375 (2018), doi
    • Characterising chordal contact B0-VPG graphs, F. Bonomo, M. P. Mazzoleni, M. L. Rean, B. Ries, Lecture Notes in Computer Science 10856, ISCO 2018, 89--100 (2018), doi
    • Graphs vertex-partitionable into strong cliques, A. Hujdurovic, M. Milanic, B. Ries, Discrete Mathematics 341(5) 1392--1405 (2018), doi
    • Dominating induced matchings in graphs containing no long claw, A. Hertz, V. Lozin, B. Ries, V. Zamaraev, D. de Werra, Journal of Graph Theory 88(1) 18--39 (2018), doi
    • On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, L. Alcon, F. Bonomo, G. Duran, M. Gutierrez, M. P. Mazzoleni, B. Ries, M. Valencia-Pabon, Discrete Applied Mathematics 234 12--21 (2018), doi
    • Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples, A. Hujdurovic, U. Kacar, M. Milanic, B. Ries, A.I. Tomescu, IEEE IEEE/ACM Transactions on Computational Biology and Bioinformatics 15(1) 96--108 (2018), doi
    • Contraction and Deletion Blockers for Perfect Graphs and H-free Graphs, O.Y. Diner, D. Paulusma, C. Picouleau, B. Ries, Theoretical Computer Science 746 49--72 (2018), doi
  • 2017
    • Blocking Independent Sets for H-free graphs via Edge Contractions and Vertex Deletions, D. Paulusma, C. Picouleau, B. Ries, Lecture Notes in Computer Science 10185, TAMC 2017, 470--483 (2017), doi
    • On star and biclique edge-colorings, S. Dantas, M. Groshaus, A. Guedes, R.C.S. Machado, B. Ries, D. Sasaki, International Transactions In Operational Research 24, 339--346 (2017), doi
  • 2016
    • A boundary property for upper domination, H. Aboueisha, S. Hussain, V. Lozin, J. Monnot, B. Ries, V. Zamaraev, Lecture Notes in Computer Science 9843, IWOCA 2016, 229--240 (2016), doi
    • Reducing the clique and chromatic number via edge contractions and vertex deletions, D. Paulusma, C. Picouleau, B. Ries, Lecture Notes In Computer Science 9849, ISCO 2016, 38--49 (2016), doi
    • On the ratio between maximum weight perfect matchings and maximum weight matchings in grids, G. D. da Fonseca, D. Sasaki, B. Ries, Discrete Applied Mathematics 207, 45--55 (2016), doi
    • On the Minimum and Maximum Selective Graph Coloring Problems in some Graph Classes, M. Demange, T. Ekim, B. Ries, Discrete Applied Mathematics 204, 77--89 (2016), doi
  • 2015
    • Finding a Perfect Phylogeny from Mixed Tumor Samples, A. Hujdurovic, U. Kacar, M. Milanic, B. Ries, A. I. Tomescu, Lecture Notes in Bioinformatics 9289 80--92 (2015), 15th International Workshop on Algorithms in Bioinformatics 2015 (WABI 2015), doi
    • Blockers for the stability number and the chromatic number, C. Bazgan, C. Bentz, C. Picouleau, B. Ries, Graphs and Combinatorics 31(1) 73--90 (2015), doi
    • Contraction Blockers for Graphs with Forbidden Induced Paths, O.Y. Diner, D. Paulusma, C. Picouleau, B. Ries, Lecture Notes in Computer Science 9079 194--207 (2015), 9th International Conference on Algorithms and Complexity (CIAC 2015), doi
    • Multiple referenda and multiwinner elections using Hamming distances : complexity and manipulability, Y. Amanatidis, N. Barrot, J. Lang, V. Markakis, B. Ries, Proceedings of the 14th International Conference on Autonomous Agents & Multiagent Systems (AAMAS 2015), Ordini, Elkind, Weiss, Yolum (eds) 715--723 (2015), doi
    • On some applications of the selective graph coloring problem, M. Demange, T. Ekim, B. Ries, C. Tanasescu, European Journal of Operations Research 240(2) 307--314 (2015), doi
    • Coloring graphs characterized by a forbidden subgraph, D. Paulusma, P. A. Golovach, B. Ries, Discrete Applied Mathematics 189 101--110 (2015), doi
    • On the maximum independent set problem in subclasses of subcubic graphs, V. Lozin, J. Monnot, B. Ries, Journal of Discrete Algorithms 31 104--112 (2015), doi
    • Vote par approbation pour les élections à vainqueurs multiples : une famille générale de règles, N. Barrot, J. Lang, B. Ries, Revue d’Intelligence Artificielle 29 265--291 (2015), doi
  • 2014
    • Characterizations of cographs as intersection graphs of paths on a grid, E. Cohen, M. Golumbic, B. Ries, Discrete Applied Mathematics 178 46--57 (2014), doi
    • On the complexity of the selective graph coloring problem in some special classes of graphs, M. Demange, J. Monnot, P. Pop, B. Ries, Theoretical Computer Science 541 89--102 (2014), doi
    • A note on r-equitable k-colorings of trees, A. Hertz, B. Ries, Yugoslav Journal of Operations Research 24(2) 293--298 (2014), doi
    • A dichotomy for upper domination in monogenic classes, H. AbouEisha, S. Hussain, V. Lozin, J. Monnot, B. Ries, Lecture Notes in Computer Science 8881,  COCOA 2014,  258--267 (2014), doi
    • Approval voting for committee elections: a general family of rules, N. Barrot, J. Lang, B. Ries, 19ème congrès national sur la reconnaissance de formes et l'IA (RFIA 2014), doi
  • 2013
    • Optimal edge-coloring with (edge) rate constraints, D. Dereniowski, W. kubiak, B. Ries, Y. Zwols, Networks 62(3) 165--182 (2013), doi
    • Perfectness of clustered graphs, F. Bonomo, D. Cornaz, T. Ekim, B. Ries, Discrete Optimiztaion 10 296--303 (2013), doi
    • The firefighter problem with more than one firefighter on trees, C. Bazgan, M. Chopin, B. Ries, Discrete Applied Mathematics 161 (7-8) 899--908 (2013), doi
    • On the intersection graphs of orthogonal line segments in the plane: characterization of some subclasses of chordal graphs, M. Golumbic, B. Ries, Graphs and Combinatorics 29(3) 499--517 (2013), doi
    • Packing and covering with linear programming, C. Bentz, D. Cornaz, B. Ries, European Journal of Operational Research 227(3) 409--422 (2013), doi
    • Possible winners in approval voting, N. Barrot, L. Gourves, J. Lang, J. Monnot, B.Ries, Lecture Notes in Artifical Intelligence 8176, ADT 2013, 57--70 (2013), doi
    • On the maximum independent set problem in subclasses of subcubic graphs, V. Lozin, J. Monnot, B. Ries, Lecture Notes in Computer Science 8288, IWOCA 2013, 314--326 (2013), doi
  • 2012
    • d-transversals of stable sets and vertex covers in weighted bipartite graphs, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Journal of Discrete Algorithms 17 95--102 (2012), doi
    • A note on chromatic properties of threshold graphs, B. Ries, D. de Werra, R. Zenklusen, Discrete Mathematics 312(10) 1838--1843 (2012), doi
    • Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory, B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, Y. Zwols, IEEE/ACM Transactions on Networking 20(1) 163--176 (2012), doi
    • Coloring vertices of trinagle-free graphs without forests, K. Dabrowski, V. Lozin, R. Raman, B. Ries, Discrete Mathematics 312(7) 1372--1385 (2012), doi
    • Some properties of edge intersection graphs of single bend paths in the grid, A. Asinowski, B. Ries, Discrete Applied Mathematics 212(2) 427--440 (2012), doi
    • Coloring graphs characterized by a forbidden subgraph, D. Paulusma, P.A. Golovach, B. Ries, Lecture Notes in Computer Science 7464, MFCS 2012, 443--454 (2012), doi
    • Selective graph coloring on some special classes of graphs, M. Demange, J. Monnot, P. Pop, B. Ries, Lecture Notes in Computer Science 7422, ISCO 2012, 320--331 (2012), doi
  • 2011
    • Claw-free graphs with strongly perfect complements. Fractional and Integral Version. Part 1. Basic graphs, M. Chudnovsky, B. Ries, Y. Zwols, Discrete Applied Mathematics 159(17) 1971--1995 (2011), doi
    • Claw-free graphs with strongly perfect complements. Fractional and Integral Version. Part 2. Non-trivial strip-structures, M. Chudnovsky, B. Ries, Y. Zwols, Discrete Applied Mathematics 159(17) 1996--2029 (2011), doi
    • A 2-approximation for the maximum satisfying bisection problem, B. Ries, R. Zenklusen, European Journal of Operational Research 210(2) 169--175 (2011), doi
    • Minimum d-transversals of maximum weight stable sets in trees, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Electronic Notes in Discrete Mathematics 38, EuroComb 2011, 129--134 (2011), doi
  • 2010
    • Solution methods for a scheduling problem with incompatibility and precedence constraints, F.-X. Meuwly, B. Ries, N. Zufferey, Algorithmic Operations Research 5 75--85 (2010), doi
    • Split-critical and uniquely split-colorable graphs, T. Ekim, B. Ries, D. de Werra, Discrete Mathematics and Theoretical Computer Science 12(5) 1--24 (2010), doi
    • Complexity of two coloring problems in cubic bipartite mixed graphs, B. Ries, Discrete Applied Mathematics 158 592--596 (2010), doi
    • Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on the grid, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Discrete Mathematics 310(1) 132--146 (2010), doi
    • On the use of graphs in discrete tomography, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Annals of Operations Research 175 287--307 (2010), doi
    • Coloring vertices of triangle-free graphs, K. Dabrowski, V. Lozin, R. Raman, B. Ries, Lecture Notes in Computer Science 6410, WG 2010, 184--195 (2010), doi
    • Analyzing the Performance of Greedy Maximal Scheduling via Local Poling and Graph Theory, B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, Y. Zwols, Proceedings INFOCOM 2010, 2213--2221 (2010), doi
  • 2009
    • Graph coloring with constarints on the neighborhoods, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Discrete Optimization 6 362--369 (2009), doi
    • Blockers and transversals, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, R. Zenklusen, Discrete Mathematics 309(13) 4306--4314 (2009), doi
    • Mixed graph edge coloring, H. Furmancyk, A. Kosowski, B. Ries, P. Zylinski, Discrete Mathematics 309(12) 4027--4036 (2009), doi
    • Degree-constrained edge partitionings in graphs arising from discrete tomography, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Journal of graph algorithms and applications 13(2) 99--118 (2009), doi
  • 2008
    • On a graph coloring problem arising from discrete tomography, C. Bentz, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Networks 51(4) 256--267 (2008), doi
    • On two coloring problems in mixed graphs, D. de Werra, B. Ries, European Journal of Combinatorics 29 712--725 (2008), doi
    • A tutorial on the use of graphs in discrete tomography, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, 4OR 6 101--123 (2008), doi
    • Addendum to bicolored matchings in some classes of graphs, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Graphs and Combinatorics 24(2) 127--128 (2008), doi
  • 2007
    • Coloring some classes of mixed graphs, B. Ries, Discrete Applied Mathematics 155 1--6 (2007), doi
    • Bicolored matchings in some classes of graphs, M.-C. Costa, D. de Werra, C. Picouleau, B. Ries, Graphs and Combinatorics 23(1) 47--60 (2007), doi

 

PhD students

  • Nathanael Barrot: 2012 - 2015 (currently postdoc at RIKEN Research Center in Japan)
    (co-supervisor: Jérôme Lang (Université Paris Dauphine))
  • Esther Galby: 2015 -
  • Vera Fischer: 2018 -

 

Visiting PhD students:

  • Zakir Deniz (2017, Duzce University (Turkey))
  • Pierre Hauweele (2018, Université de Mons (Belgium))
  • Paloma Thomé de Lima (2018, University of Bergen (Norway))

 

Member of PhD committees:

  • Grégoire Cotté, Conservatoire National des Arts et Métiers, Paris, France (2016)
  • Vasileios Papapanagiotu, Università della Svizzera Italiana, Lugano, Switzerland (2018)

 

Postdocs

  • Diana Sasaki: 2014 - 2015 (now Professor at Universidade do Estado do Rio de Janeiro (Brazil))
  • Maria Pia Mazzoleni: August 2017 (now Docencia at Universidad Nacional La Plata (Argentina))
  • Andrea Munaro: February - June 2018 (now Visiting Assistant Professor at Wesleyan University (US))

 

Third Party Funding

  • 2018 : Funding from private sector (Schwendimann AG); Effiziente und nachhaltige Kehrichtsammlung
  • 2015 : PHC Proteus grant; Structural and Algorithmic Aspects of Graph Classes Defined by Cliques and Stable Sets
  • in collaboration with Slovenian researchers; role: coordinator
  • 2014 : MATH-AmSud grant; Discrete mathematics: graph partition problems
    in collaboration with Brazilian researchers; role: coordinator
  • 2013 : MATH-AmSud grant; Algorithmic, Algebraic and Structural issues on coloring and matching theory of graphs
    in collaboration with Argentinian and Chilean researchers; role: member
  • 2012 : GdR - Recherche Opérationnelle grant; Décoloration: d-bloqueur minimum pour le nombre chromatique d'un graphe
    in collaboration with French researchers; role: member
  • 2012 : PHC Bosphore grant; The selective graph coloring problem
    in collaboration with Turkish researchers; role: coordinator
  • 2012 : GdR - Recherche Opérationnelle grant; Problèmes de coloration avec sélection
    in collaboration with French researchers; role: coordinator
  • 2008 : FNR (Luxembourg) grant for postdoctoral research at Columbia University

 

Conference activities