Gwenaël Joret PhD in Computer Science Postdoctoral Researcher of the F.R.S.-FNRS, Université Libre de Bruxelles Curriculum Vitae

Contact

Université Libre de Bruxelles Département d'Informatique, CP 212 Boulevard du Triomphe 1050 Bruxelles Belgium

Office: O8.101 Phone: (+32) (0)2 650 58 75 E-mail: gjoret 'at' ulb 'dot' ac 'dot' be

Teaching

Enoncés des exercices pour le cours Graphes et Réseaux (INFO-F-521).

Publications

• Excluded forest minors and the Erdős-Pósa property. With S. Fiorini and D. R. Wood.
• A linear-time algorithm for finding a complete graph minor in a dense graph. With V. Dujmović, D. J. Harvey, B. Reed, and D. R. Wood.
• Nonrepetitive colourings of planar graphs with O(logn) colours. With V. Dujmović, F. Frati, and D. R. Wood.
• Nonrepetitive colouring via entropy compression. With V. Dujmović, J. Kozik, and D. R. Wood.
• A note on the Cops & Robber game on graphs embedded in non-orientable surfaces. With N. E. Clarke, S. Fiorini, and D. O. Theis.
• An improved bound for First-Fit on posets without two long incomparable chains. With V. Dujmović and D. R. Wood. SIAM Journal on Discrete Mathematics, accepted pending minor revisions.
• Boxicity of graphs on surfaces. With L. Esperet. Graphs and Combinatorics, to appear.
• Complete graph minors and the graph minor structure theorem. With D. R. Wood. Journal of Combinatorial Theory, Series B, accepted pending minor revisions.
• Sorting under partial information (without the ellipsoid algorithm). With J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro. Combinatorica, accepted pending minor revisions. Extended abstract in proc. of STOC 2010.
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs. With J. Cardinal, E. D. Demaine, S. Fiorini, I. Newman, and O. Weimann. Journal of Combinatorial Optimization, accepted. Extended abstract in proc. of WINE 2009.
• Nordhaus-Gaddum for treewidth. With D. R. Wood. European Journal of Combinatorics, 33/4:488--490, 2012.
• Approximating the balanced minimum evolution problem. With S. Fiorini. Operations Research Letters, 40/1:31--35, 2012.
• Small minors in dense graphs. With S. Fiorini, D. O. Theis, and D. R. Wood. European Journal of Combinatorics, 33/6:1226--1245, 2012.
• Trees with given stability number and minimum number of stable sets. With V. Bruyère and H. Mélot. Graphs and Combinatorics, 28/2:167--187, 2012.
• Minimum entropy combinatorial optimization problems. With J. Cardinal and S. Fiorini. Theory of Computing Systems, 51/1:4--21, 2012. Extended abstract in proc. of CiE 2009.
• Disproof of the list Hadwiger conjecture. With J. Barát and D. R. Wood. Electronic Journal of Combinatorics, 18/1:R232, 2011.
• Hitting and harvesting pumpkins. With C. Paul, I. Sau, S. Saurabh, and S. Thomassé. Extended abstract in proc. of ESA 2011.
• First-Fit is linear on posets excluding two long incomparable chains. With K. G. Milans. Order, 28/3:455--464, 2011.
• On the maximum number of cliques in a graph embedded in a surface. With V. Dujmović, G. Fijavž, T. Sulanke, and D. R. Wood. European Journal of Combinatorics, 32/8:1244--1252, 2011.
• Stackelberg network pricing is hard to approximate. Networks, 57/2:117--120, 2011.
• The Stackelberg minimum spanning tree game. With J. Cardinal, E. D. Demaine, S. Fiorini, S. Langerman, I. Newman, and O. Weimann. Algorithmica, 59/2:129--144, 2011. Extended abstract in proc. of WADS 2007.
• Hitting diamonds and growing cacti. With S. Fiorini and U. Pietropaoli. Extended abstract in proc. of IPCO 2010.
• Irreducible triangulations are small. With D. R. Wood. Journal of Combinatorial Theory, Series B, 100/5:446--455, 2010.
• An efficient algorithm for partial order production. With J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro. SIAM Journal on Computing, 39/7:2927--2940, 2010. Extended abstract in proc. of STOC 2009.
• The Cops and Robber game on graphs with forbidden (induced) subgraphs. With M. Kamiński and D. O. Theis. Contributions to Discrete Mathematics, 5/2:40--51, 2010.
• Weighted graphs defining facets: a connection between stable set and linear ordering polytopes. With J.-P. Doignon and S. Fiorini. Discrete Optimization, 6/1:1--9, 2009.
• On a theorem of Sewell and Trotter. With S. Fiorini. European Journal of Combinatorics, 30/2:425--428, 2009.
• Minimum entropy orientations. With J. Cardinal and S. Fiorini. Operations Research Letters, 36/6:680--683, 2008.
• Well-balanced orientations of mixed graphs. With A. Bernáth. Information Processing Letters, 106/4:149--151, 2008.
• Turán’s theorem and k-connected graphs. With N. Bougard. Journal of Graph Theory, 58/1:1--13, 2008.
• Tight results on minimum entropy set cover. With J. Cardinal and S. Fiorini. Algorithmica, 51/1:49--60, 2008. Extended abstract in proc. of APPROX 2006.
• Minimum entropy coloring. With J. Cardinal and S. Fiorini. Journal of Combinatorial Optimization, 16/4:361--377, 2008. Extended abstract in proc. of ISAAC 2005.
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs. With J.-P. Doignon and S. Fiorini. Journal of Mathematical Psychology, 50/3:251--262, 2006.