András Sebő

Equipe Optimisation Combinatoire, Grenoble (link not yet available)

 

 

Portrait

bureau C308
46,  avenue Félix Viallet
38000 Grenoble
France

T:+33  (0) 4 76 57 48 99,   (0) 4 56 40 31 75
mail

Last update: August 2008.  Remarks are welcome 

Popularization       Publications          Lectures

(I may be able to send electronic reprints, if requested.)

 

Main  topics  :         Combinatorial Optimization, Polyhedral Combinatorics, Graphs

Some links   :          EGRES,  C&O,   CWI,  MIT , Bonn,  LL

 

Popularization, Theses

  • Combinatorial search problems, M.S. thesis, 1979, (in Hungarian).
  • Solution of timetable problems with network flow methods, Ph.D. thesis, Eötvös Loránd University, 1983, (in Hungarian).
  • Graph factors: Structures and Algorithms, Thesis for the 'Candidate of Sciences' degree (in Hungarian), 1987.
  • `Peut-on trouver ce qu'on peut prouver ?', 'La Recherche', numéro spécial `Mathématiques', octobre 2001 (in French)
  • Les quarante deux ans de la conjecture de Berge ','La Recherche', 'Hors Série' entitled 'La Preuve Scientifique', (in French) Juillet-Aoűt-Septembre 2002 , encadré ajouté ŕ la republication de 'Peut-on trouver ce qu'on peut prouver'.
  • Le charme discret des mathématiques, Image des mathématiques, Publication CNRS, édition 2006. (in French)   --- download pdf
  • Parcours et Coupes, (with Frédéric Meunier), Chapter in "Graphes et Applications", textbook, Hermes (Jean-Claude Fournier ed), 2006.

 

Selected Publications

Structures and Algorithms in Combinatorial Optimization

  • Finding the t-join structure of graphs, Mathematical Programming , 36, 1986, 123-134.
  • Undirected shortest paths and the postman-structure of graphs, Journal of Combinatorial Theory/B, 49, No 1, June 1990
  • Recognizing Greedy Structures, Journal of Algorithms, 20, 1996, 137--156 (with Y.Caro and M.Tarsi).
  • The Path Packing Structure of Graphs Integer Programming and Combinatorial Optimization 10, New York Columbia (D. Bienstock ed.), June 2004, (with László Szegő).
  • A Berge-keeping operation for Graphs, volume in honor of Claude Berge edited by A. Bondy and V. Chvátal, Discrete Mathematics 306 (2006), 2582--2592.

 

Matchings in Graphs and Generalizations, Multiflows

  • A quick proof of Seymour's theorem on T-joins, Discrete Mathematics , 64, 1987, 101-103.
  • Covering directed and odd cuts, Mathematical Programming Study, 22, 1984, 99-112 (in common with András Frank and Éva Tardos)
  • Cographic multicommodity flow problems: an epilogue, DIMACS Vol 1, Polyhedral Combinatorics (W. Cook and P. D. Seymour AMS, ACM eds., 1991).
  • Circuit packings in graphs embedded into surfaces with at most three cross-caps, in ``Integer Programming and Combinatorial Optimization III'', Rinaldi and Wolsey editors, Centro Ettore Majorana, Erice (1993).
  • General antifactors of graphs, Journal of Combinatorial Theory , Series B, 58, 2, July 1993.
  • Plane multiflows with a fixed number of demands, Journal of Combinatorial Theory/B , 59,163-171, Novembre 1993.
  • A generalized cut condition for multiflows in matroids, (with Werner Schwärzler), Discrete Mathematics , 113, (1993) 207-221.
  • On multiflow maximization, SIAM Journal of Discrete Mathematics, February 1997, 158-170, (with A.Frank and A.Karzanov).
  • Potentials in Undirected Graphs and Planar multiflows, SIAM J. Computing, March 1997, 582-603
  • On integer multiflows and metrics in binary Matroids, in `Combinatorics and Computer Science', Lecture Notes in Computer Science 1120 (Springer), 1997, 218-233 (with K. Marcus).
  • Integer multiflows and metric packings beyond the cut condition (common with Karina Marcus), Discrete Mathematics, 239 (1-3) (2001) pp. 13-31
  • Connected Joins in Graphs, (joint work with Eric Tannier), Integer Programming and Combinatorial Optimization, LNCS 2081, May 2001.
  • Minsquare Factors and Maxfix Covers of Graphs (with Nicola Apollonio), Integer Programming and Combinatorial Optimization 10, New York Columbia (D. Bienstock ed.), June 2004.
  • Multiflows and Klein’s bottle (with Bert Gerards, in preparation)
  • Disjoint Paths Problems: an Annotated Tableau (with Guyslain Naves), accepted for William Cook, László Lovász, Jens Vygen (Editors), Research  Trends in Combinatorial Optimization.Springer, Berlin 2009, The original publication is available at www.springer.com/978-3-540-76795-4

 

Polyhedral Combinatorics, Packing, Covering

  • Covering directed and odd cuts, Mathematical Programming Study, 22, 1984, 99-112 (with András Frank and Éva Tardos)
  • Total dual integrality implies local strong unimodularity, (with Bert Gerards), Mathematical Programming , 38 (1987), 69-73.
  • Dual integrality in parity constrained subgraph polyhedra, in ''Infinite and Finite Sets" (eds.: Hajnal, T. Sós) Proceedings of the conference held in Eger, July 1987.
  • The Schrijver system of odd join polyhedra, Combinatorica , 8 (1) (1988), 103-116.
  • Hilbert bases, Caratheodory's theorem and Combinatorial Optimization, in ``Integer Programming and Combinatorial Optimization I'', University of Waterloo Press, R. Kannan and W. Pulleyblank eds, ISBN 0-88898-099-X, (1990).(download ps file)
  • On Ideal Clutters, Metrics and Multiflows, in ``Integer Programming and Combinatorial Optimization 5'', Springer Verlag, Lecture Notes in Computer Science, 1084, June 1996 (Vancouver), (with Beth Novick).
  • Characterizing Noninteger Polyhedra with 0-1 constraints, in ``Integer Programming and Combinatorial Optimization 6'', Springer Verlag, Lecture Notes in Computer Science, 1412, June 1998 (Houston).
  • An introduction to empty lattice-simplices, in Lecture Notes in Computer Science 1610, (Cornu\'ejols, Burkard, Woeginger Eds.), Springer, June 1999.
  • Integer Polyhedra: Combinatorial Properties and Complexity (semi-plenary lecture and survey paper for the International Symposium on Mathematical Programming in Atlanta, august 2000), accepted draft cf. Cahiers du Laboratoire Leibniz, 2001.
  • Imperfect and nonideal clutters: a common approach, (with M. Preissmann and G. Gasparyan), Combinatorica, 23 (2) (2003) 283--302
  • Minmax Theorems in Cyclically Ordered Graphs,   Journal of Combinatorial Theory/B, 97 (4), July 2007.
  • Paintshop, Necklaces and Combinatorial Optimization (with Frédéric Meunier), Discrete Applied Mathematics (2008),
  • doi:10.1016/j.dam.2008.06.017 2008.
  • Cyclic Orders: Equivalence and Duality (with Pierre Charbit), Combinatorica 28 (2) (2008) 131–143

 

Coloring

  • The clique rank and the coloration of perfect graphs, (in common with Jean Fonlupt), in ``Integer Programming and Combinatorial Optimization I , University of Waterloo Press, R. Kannan and W. Pulleyblank eds, (1990). --- download scanned pdf
  • Forcing Colorations and the Perfect graph conjecture, in ``Integer Programming and Combinatorial Optimization II'', Balas, Cornuéjols, Kannan eds, (1992), Carnegie Mellon University Press.
  • On critical edges in minimal imperfect graphs, Journal of Combinatorial Theory, B, 67, (1996), 62--85.
  • On the connectivity of minimal imperfect graphs, Journal of Graph Theory , 23, 1996, 77-85
  • Coloring Precolored Perfect Graphs, Journal of Graph Theory, 25 (3), 1997, pp. 207-216 (with Jan Kratochvíl)
  • Flows, View Obstructions and the Lonely Runner, Journal of Combinatorial Theory, 72, 1, January 1998, (with W. Bienia, L. Goddyn, P. Gwozdiak, M. Tarsi).
  • Directed Versions of the Graham-Pollak Theorem, Cahiers du Laboratoire Leibniz  , Octobre 2000.
  • Some aspects of minimally imperfect graphs, (with Myriam Preissmann), Chapter in Ramirez Alfonsin, J.L.(ed.); Reed, Bruce (ed.) Perfect graphs. Chichester: Wiley, (2001), pages 185--214.
  • Coloring the maximal cliques of graphs, SIAM Journal on Discrete Mathematics 17 (2004), 3, pp. 361-376, (with Bacsó, Gyárfás, Gravier, Preissmann)  SIAM Journal of Discrete Mathematics, Vol 17, No 3, pp 361-376

 

Scheduling, Approximation and other Applications

  • A Particular Timetable Problem: Terminal Scheduling, Computers and Mathematics , vol 21, 1, 1991 (Selection of Hungarian Applied Mathematics).
  • Optimal cuts in graphs and statistical mechanics, Journal of Mathematical and Computer Modelling, Vol 26, No 8-10, 1997, pp. 1-11, (with J. C. Anglčs d'Auriac and M. Preissmann).
  • An improved approximation algorithm for minimum size 2-edge connected spanning subgraph, in ``Integer Programming and Combinatorial Optimization 6'', Springer Verlag, Lecture Notes in Computer Science, 1412, June 1998, (with J. Cheriyan, and Z. Szigeti)
  • Approximation algorithms and ear decompositions of graphs (in common with Cheriyan and Szigeti), SIAM J. Discrete Math. Vol 14, No 2 (2001), pp 130-180
  • Optimal Cooperation and computing Pott's partition function with a large number of states, in common with Myriam Preissmann, Jean-Christian Angl\`es-d'Auriac and Ferenc Iglói, Journal of Theoretical Physics, 2002.
  • Batch Processing with Interval Graph Compatibilities Between Tasks , Discrete Applied Mathematics, Volume 156, issue 5, March 2008, pp 556-568 (with Gerd Finke, Vincent Jost and Maurice Queyranne).
  • Graphic Submodular Function Minimization:a Graphic Approach and Applications, (with Myriam Preissmann),accepted for William Cook, László Lovász, Jens Vygen (Editors): Research Trends in Combinatorial Optimization.Springer, Berlin 2009, The original publication is available at www.springer.com/978-3-540-76795-4

 

General Combinatorics  (Group Testing, Metric Reconstruction, Diversity)

  • Sequential Search using question sets with bounded intersections, Journal of Statistical Planning and Inference , 7, 1982, 932-156
  • On two random search problems, Journal of Statistical Planning and Inference , 11, 1985, 23-31
  • On the geodesic structure of graphs: a polyhedral approach to metric decomposition, in ``Integer Programming and Combinatorial Optimization III'', Rinaldi and Wolsey editors, Centro Ettore Majorana, Erice (1993), (in common with Michael Lomonosov).
  • Optimal binary trees with order constraints (in common with Zeev Vaxman), Discrete Applied Mathematics, 91 (1998) 305--311.
  • The metric dimension of Graphs, (with Eric Tannier), Mathematics of Operations Research, (29), 2 (May 2004), pp 383--393.
  • Optimizing Diversity, extended abstract in Electronic Notes in Discrete Mathematics 29 (2007) 73-77, accepted for Combinatorics, Probability and Computing, 2008 (with Yannick Frein and Benjamin Lévęque).

 

Courses and Lectures (selection of downoadable files)