This is an invitation to the next "UHH Informatik Kolloquium"
http://www.inf.uni-hamburg.de/de/home/news/kolloquium/sose14.html
SPEAKER:
Professor Dr. Petra Mutzel
Lehrstuhl für Algorithm Engineering
Technische Universität Dortmund
http://ls11-www.cs.uni-dortmund.de/staff/mutzel
This talk will be in German or English, according to preference.
DATE:
MONDAY, 23.06.2014, 17:15 s.t.
PLACE:
Konrad-Zuse-Hörsaal, Informatikum, B-201
http://www.inf.uni-hamburg.de/de/service/location
-------------------------------------------------------------------
TOPIC: Recent Advances in Crossing Minimization
-------------------------------------------------------------------
ABSTRACT:
The crossing number problem asks for the minimum number of edge crossings
that can be achieved by drawing a given graph in the 2-dimensional plane.
It has originally been stated by Turan during the second world war and
published in 1954. Since then, many interesting theoretical and practical
results have been obtained. We will survey some of the more recent
results. Despite the many published papers on this problem and its
variants, the crossing number is only known for very few graph classes.
Although the Harary-Hill conjecture provides a closed formula for the
crossing number of complete graphs, it has only been settled for graphs
with up to 12 vertices. We will review recent results and present further
progress concerning the crossing number of complete graphs. We will
discuss why many experts think that the new approaches will have the
strength to settle this open problem. For general graphs, we will present
approaches based on integer linear programming formulations for computing
the exact crossing number. Our branch-and-cut algorithms are able to
compute the exact crossing numbers for general sparse graphs with up to
100 vertices and crossing number up to 37 within 30 minutes. We will also
survey recent approximation results for the crossing number. For general
graphs, no polynomial time algorithm is known approximating the crossing
number within some non-trivial factor. However, for certain graph classes
like ³almost planar graphs² of bounded degree, the crossing number can be
approximated by a constant factor.
BIO:
Professor Dr. Petra Mutzel has studied Mathematics at Universität
Augsburg. After her Ph.D. in Computer Science, which she received 1994 at
the Universität zu Köln, she was member of the Max-Planck-Institut für
Informatik in Saarbrücken, where she also got her habilitation in 1999.
After a temporary professorship at the Universität Heidelberg, she got a
full professorship for Algorithms and Data Structures at the Technische
Universität Wien. Since 2004, she is full professor for Algorithm
Engineering at the Technische Universität Dortmund. She is Associate
Editor of the Journal of Graph Algorithms and Applications (JGAA),
Mathematical Programming Computation (MPC), the EURO Journal on
Computational Optimization, the Graph Drawing E-print Archive, and the ACM
Journal on Experimental Algorithmics. In the year 2000, she got the
research prize ³Technische Kommunikation 2000² by the Alcatel SEL Stiftung
für Kommunikationsforschung. Her research focuses on combinatorial
optimization problems as well as on graph data structures and algorithms
with the main application areas graph drawing, network design, and
cheminformatics.
CONTACT:
Prof. Dr. Ulrike von Luxburg
Department of Computer Science, University of Hamburg
Phone: +49-(0)40-42883-2409
http://www.informatik.uni-hamburg.de/ML/contents/people/luxburg/
_______________________________________________
Kolloquium mailing list
Kolloquium@mailhost.informatik.uni-hamburg.de
https://mailhost.informatik.uni-hamburg.de/mailman/listinfo/kolloquium
_______________________________________________
HiForum-Verteiler mailing list
HiForum-Verteiler@mailhost.informatik.uni-hamburg.de
https://mailhost.informatik.uni-hamburg.de/mailman/listinfo/hiforum-verteiler