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

ORCID iD iconORCID

 

 

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 

Several of my publications which are not directly available through Open Access on the journals' webpage can be found on our institutional repository according to the Open Access policies of the journals.

  • Submitted / to appear
    • Finding Matching Cuts in H-Free Graphs, F. Lucke, D. Paulusma, B. Ries, to appear in Algorithmica (journal version)

    • Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius, F. Lucke, D. Paulsma, B. Ries, submitted (available on arxiv)

    • Finding k-community structures in special graph classes, N. Baghirova, C. Dallard, B. Ries, D. Schindl, submitted (available on arxiv). 

  • 2023
    • Using edge contractions to reduce the semitotal domination number, E. Galby, F. Mann, P.T. Lima, B. Ries, Theoretical Computer Science 939 (2023) 140 - 160 Open Access 
  • 2022
    • On some special classes of contact B0-VPG graphs, F. Bonomo, M. P. Mazzoleni, M. L. Rean, B. Ries, Discrete Applied Mathematics 308 111 - 129, doi
    • On The Complexity of Matching Cut for Graphs of Bounded Radius and H-Free Graphs, F. Lucke, D. Paulusma, B. Ries,  Theoretical Computer Science 936 (2022) 33-42  Open Access
    • Finding Matching Cuts in H-Free Graphs, F. Lucke, D. Paulusma, B. Ries, Leibniz International Proceedings in Informatics 248 22:1 - 22:16 (2022), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) Open Access
    • Locally checkable problems parameterized by clique-width, N. Baghirova, C. Gonzalez, B. Ries, D. Schindl, Leibniz International Proceedings in Informatics 248 31:1 - 31:20 (2022), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) Open Access
  • 2021
    • Reducing the domination number of graphs via edge contractions and vertex deletions, E. Galby, P.T. Lima, B. Ries, Discrete Mathematics 344(1) 112169 (available through Open Access)
    • CPG graphs: some structural and hardness results, N. Champseix, E. Galby, A. Munaro, B. Ries, Discrete Applied Mathematics 290 17-35 (available through Open Access)
    • On Some Subclasses of Split B1-EPG Graphs, Deniz, S. Nivelle, B. Ries , D. Schindl (2020), In Kohayakawa Y., Miyazawa F.K. (eds) LATIN 2020: Theoretical Informatics. LATIN 2021. Lecture Notes in Computer Science, vol 12118. Springer, Cham., doi
    • Blocking total dominating sets via edge contractions, E. Galby, F. Mann, B. Ries, Theoretical Computer Science 877 18-35 (available through  Open Access)
    • Reducing the domination number of $P_3+kP_2$-free graphs via one edge contraction, E. Galby, F. Mann, B. Ries, Discrete Applied Mathematics 305 205-210 (available through Open Access)
  • 2020

    • Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width, E. Galby, A. Munaro, B. Ries, Theoretical Computer Science 814 28-48, doi

  • 2019
    • On contact graphs of paths in  grid, Z. Deniz, E. Galby, A. Munaro, B. Ries, Lecture Notes in Computer Science 11282, Graph Drawing 2018, 317--330 (2019), doi
    • Critical Vertices and Edges in H-free Graphs, D. Paulusma, C. Picouleau, B. Ries, Discrete Applied Mathematics 257 361--367 (2019), doi
    • Classifying k-edge colouring for H-free graphs, E. Galby, P. T. Lima, D. Paulusma, B. Ries, Information Processing Letters 146 39--43 (2019), doi 
    • Proper circular arc graphs as intersection graphs of paths in a grid, E. Galby, M.P. Mazzoleni, B. Ries, Discrete Applied Mathematics  262 195-202 (2019), doi
    • Detecting strong cliques, A. Hujdurovic, M. Milanic, B. Ries, Discrete Mathematics 342 2738-2750, doi
    • Reducing the domination number of graphs via edge contractions, E. Galby, P.T. Lima, B. Ries, Leibniz International Proceedings in Informatics 138 41:1 - 41:13 (2019), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019),  doi
    • Maximum Eccentric Connectivity Index for Graphs with given Diameter, P. Hauweele, A. Hertz, H. Mélot, B. Ries, G. Devillez, Discrete Applied Mathematics 268 102-111, doi
    • Blocking dominating sets for H-free graphs via edge contractions, E. Galby, P. T. Lima, B. Ries, Leibniz International Proceedings in Informatics 149 21:1 - 21:14 (2019), 30th International Symposium on Algorithms and Computation (ISAAC 2019),  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 - 2020 (currently Postdoc at Technische Universität Hamburg, Germany)
  • Vera Fischer: 2018 - 2023 (co-supervision with Meritxell Pacheco)
  • Felix Mann: 2019 -
  • Felicia Lucke: 2020 -
  • Narmina Baghirova: 2020 - (co-supervision with David Schindl)
  • Elise Bangerter: 2023 - (co-supervision with Meritxell Pacheco)

 

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))
  • Carolina Goncalvez (20021, 2022, University of Buenos Aires (Argentina))

 

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)
  • Gauvain Devillez, Université de Mons, Belgium (2022)
  • Nikolaos Melissinos, Université Paris Dauphine PSL, France (2022)
  • Valentin Bouquet, Conservatoire National des Arts et Métiers, Paris, France (2022)
  • Pierre Hauwelee, Université de Mons, Belgium (2023)

 

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 Lecturer at Queen's University Belfast (UK))
  • Zakir Deniz: September - December 2019
  • Meritxell Pacheco: January 2021 - August 2021 (now Senior Researcher and Lecturer at University of Fribourg (CH))
  • Jérôme De Boeck: March 2022 - ongoing

 

Third Party Funding

  • 2022: SBB Research Fund; Optimization of train crew assignemnt to activity segments
  • 2019 - 2022 : Innosuisse project 36157.1 IP-EE; Decision support for an efficient and sustainable waste collection; role: PI
  • 2019 : Funding from private sector; Planungsunterstützung 
  • 2018 : Funding from private sector; Effiziente und nachhaltige Kehrichtsammlung
  • 2015 - 2016 : PHC Proteus grant; Structural and Algorithmic Aspects of Graph Classes Defined by Cliques and Stable Sets
  • in collaboration with Slovenian researchers; role: coordinator
  • 2014 - 2015 : MATH-AmSud grant; Discrete mathematics: graph partition problems
    in collaboration with Brazilian researchers; role: coordinator
  • 2013 - 2014 : 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 -2013 : 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