Lehrstuhl für Theoretische Informatik


Dr. Torsten Tholey

 Postal Address:
Dr. Torsten Tholey
Lehrstuhl für Theoretische Informatik
Institut für Informatik
Universität Augsburg
D-86135 Augsburg

 House Address:
Raum 3071
Universitätsstr. 6a, 2. Stock
D-86159 Augsburg

 Research Interests:

            Graph Algorithms
            Combinatorial Optimization



  Papers: The copyright of all published papers is held by Springer unless explicitely marked otherwise. All conference versions that appeared in LNCS can be found here. For the journal paper follow the link to the journal homepage.

2013
Intersection GraphsFrank Kammer und Torsten Tholey: Approximation Algorithms for Intersection Graphs. To appear in Algorithmica. Abstract

The online version is already available at www.springerlink.com.

                      
2012
Disjoint path on acyclic graphsTorsten Tholey: Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science 465, 35-48 (2012). Copyright by Elsevier. Abstract

The original publication is available at www.sciencedirect.com.

                      
Planar treewidth
Frank Kammer and Torsten Tholey: Approximate Tree Decompositions of Planar Graphs in Linear Time. SODA 2012, 683-698. Copyright by SIAM. Abstract

The original publication is available at siam.omnibooksonline.com/2012SODA.

                      
Networks
Frank Kammer and Torsten Tholey: The Complexity of Minimum Convex Coloring. Discrete Applied Mathematics 160(6), 810-833 (2012). Copyright by Elsevier. Abstract

The original publication is available at www.sciencedirect.com.

                      
2011
Planar treewidth
Frank Kammer and Torsten Tholey: Approximate Tree Decompositions of Planar Graphs in Linear Time.arXiv.org. CORR abs/1104.2275. Abstract

The original publication is available at arxiv.org/abs/1104.2275.

   
2010
Intersection GraphsFrank Kammer, Torsten Tholey, and Heiko Voepel: Approximation Algorithms for Intersection Graphs. LNCS 6302. Approx 2010, 260-273. Abstract

The original publication is available at www.springerlink.com.

Intersection
Graphs 
2009
DPP on Chordal GraphsFrank Kammer, Torsten Tholey: The k-Disjoint Paths Problem on Chordal Graphs. LNCS 5911. WG 2009, 190-201. Abstract

The original publication is available at www.springerlink.com.

DPP on Chordal Graphs
2DPP on planar graphs Torsten Tholey: Improved Algorithms for the 2-Vertex Disjoint Paths Problem. LNCS 5404. SOFSEM 2009, 546-557. Abstract

The original publication is available at www.springerlink.com.

2DPP on planar graphs 
Networks
Frank Kammer and Torsten Tholey. A Lower Bound for the Treewidth of k-Outerplanar Graphs. Uni Augsburg, Report 2009-7, 2009. Abstract treewidth of k-outer graphs
2008
Convex ColoringFrank Kammer, Torsten Tholey: The Complexity of Minimum Convex Coloring. LNCS 5369. ISAAC 2008, 16-27. Abstract

The original publication is available at www.springerlink.com.

Convex Coloring
2007
2ddp-nearlyLinear Torsten Tholey: Effiziente Algorithmen und Datenstrukturen zur Berechnung zweier disjunkter Pfade. Dr. Thesis published by dissertation.de. Copyright by Torsten Tholey.                       
2006
2ddp-nearlyLinear Torsten Tholey: Solving the 2-Disjoint Paths Problem in Nearly Linear Time. Theory Comput. Syst. 39(1): 51-78 (2006). Abstract

The original publication is available at www.springerlink.com.

k-outerplanar                      
2005
DPP-acyclic Torsten Tholey: Finding Disjoint Paths on Directed Acyclic Graphs. LNCS 3787. WG 2005, 319-330. Abstract

The original publication is available at www.springerlink.com.

... 
2004
2DPP Torsten Tholey: Solving the 2-Disjoint Paths Problem in Nearly Linear Time. LNCS 2996. STACS 2004, 350-361. Abstract

The original publication is available at www.springerlink.com.

... 
2003
DPP-digraph Torsten Tholey: A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs. LNCS 2906. ISAAC 2003, 565-574. Abstract

The original publication is available at www.springerlink.com.

... 
2001
hashing Torben Hagerup, Torsten Tholey: Efficient Minimal Perfect Hashing in Nearly Minimal Space. LNCS 2010. STACS 2001, 317-326. Abstract

The original publication is available at www.springerlink.com.

... 


                      

  Teaching: Unless explicitely marked otherwise, all slides and lectures notes are written in German.

WS 11/12
Diskrete Strukturen für Informatiker

Lecture notes and slides can be found here.
SS 11
Mini-course "Finding Disjoint Paths in Graphs"

at the University of Leicester (September 2011)

My english slides can be found here.
Graphenalgorithmen für Pfad- und Zusammenhangsprobleme

My lecture notes and slides can be found here.
(Algorithmen und Datenstrukturen assistant to Prof. Dr. Torben Hagerup)
WS 10/11
Graphenalgorithmen für spezielle Graphen

My lecture notes and slides can be found here.
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
SS 10
Graphenalgorithmen für Pfad- und Zusammenhangsprobleme

My lecture notes and slides can be found here.
Einführung in die Algorithmische Geometrie (assistant to Prof. Dr. Torben Hagerup)
Einführung in die Theoretische Informatik (assistant to Prof. Dr. Torben Hagerup)
WS 09/10
Algorithmen für NP-harte Probleme (assistant to Prof. Dr. Torben Hagerup)
Einführung in die Komplexitätstheorie (assistant to Prof. Dr. Torben Hagerup)
SS 09
Multikriteria-Optimierung

My slides can be found here.
Flüsse in Netzwerken (assistant to Prof. Dr. Torben Hagerup)
WS 08/09
Graphenalgorithmen für spezielle Graphen

My lecture notes and slides can be found here.
SS 08
Graphenalgorithmen für Pfad- und Zusammenhangsprobleme

My lecture notes and slides can be found here.
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
WS 07/08
Graphenalgorithmen für spezielle Graphen

My lecture notes and slides can be found here.
SS 07
Graphenalgorithmen für Pfad- und Zusammenhangsprobleme

My lecture notes and slides can be found here.
Einführung in die Theoretische Informatik (assistant to Prof. Dr. Torben Hagerup)
WS 06/07
Graphenalgorithmen für spezielle Graphen

My lecture notes and slides can be found here.
SS 06
Graphenalgorithmen für Pfad- und Zusammenhangsprobleme

My lecture notes and slides can be found here.
Einführung in die Theoretische Informatik (assistant to Prof. Dr. Torben Hagerup)
SS 05
Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
WS 04/05
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)


External links are selected and reviewed when they are added to my page. However, I am not responsible for the content of external websites.