Lehrstuhl für Theoretische Informatik


Dr. Frank Kammer

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

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

 Telefon:
0049 - 821 - 598 - 2381

 Email:


 Research Interests:

            Space-Eff. Algorithms
            Graph Algorithms
            FPT Algorithms
            Tree Decompositions
            Planar Graphs
            MSO Logics
            Temporal Graphs

 My Publications:  PDF






  Conference Papers: The original publications of all LNCS Papers below are available at www.springerlink.com and the copyright is held by Springer.

2017
Space-Efficient Euler Partition and Bipartite Edge Coloring
Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-Efficient Euler Partition and Bipartite Edge Coloring CIAC 2017, to appear. Abstract 
2016
Space-Efficient  Line-Sweep Algorithms
Amr Elmasry and Frank Kammer. Space-Efficient Line-Sweep Algorithms. ISAAC 2016, pp. 30:1-30:13. Abstract 
Space-Efficient Hidden Surface Removal
Frank Kammer, Maarten Löffler und Rodrigo I. Silveira. Space-Efficient Hidden Surface Removal. Massive 2016. Abstract 
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
Frank Kammer, Dieter Kratsch und Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. MFCS 2016: pp. 190-201. AbstractSpace-Efficient Biconnected Components and Recognition of Outerplanar Graphs 
2015
On Temporal Graph Exploration
Thomas Erlebach, Michael Hoffmann und Frank Kammer. On Temporal Graph Exploration. ICALP 2015: pp. 444-455. Abstract  
Space-efficient Basic Graph Algorithms
Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. STACS 2015: pp. 288-301. AbstractSpace-Eff. Graoh Algorithms 
2014
Cheapest Set Problems under Uncertainty
Thomas Erlebach, Michael Hoffmann, and Frank Kammer. Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty. MFCS 2014: pp. 263-274. AbstractCheapest Set
Guarding
Frank Kammer, Maarten Löffler, Paul Mutser, and Frank Staals. Practical Approaches to Partially Guarding a Polyhedral Terrain. GIScience 2014: pp. 318-332. AbstractGuarding Terrain
2013
maxleaf
Frank Kammer. A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem. WG 2013 : pp. 310-320. Abstractmaxleaf
2012
Networks
Frank Kammer and Torsten Tholey. Approximate Tree Decompositions of Planar Graphs in Linear Time. SODA 2012: pp. 683-698. Abstract  
2011
Planar Dominating Set
Rene van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier and Mathias Weller. Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs. IPEC 2011: pp. 194-206. AbstractKernel Planar Dominating Set
Sensor Cover
Thomas Erlebach, Tom Grant, and Frank Kammer. Maximising Lifetime for Fault-Tolerant Target Coverage in Sensor Networks SPAA 2011, pp. 187-196. Abstract 
2010
Intersection Graphs
Frank Kammer, Torsten Tholey, and Heiko Vöpel. Approximation Algorithms for Intersection Graphs. Approx 2010, pp. 260-273. AbstractIntersection
Graphs 
Imprecise Terrains
Chris Gray, Frank Kammer, Maarten Löffler, and Rodrigo I. Silveira. Removing Local Extrema from Imprecise Terrains. EuroCG 2010 and CoRR abs/1002.2580 (2010). AbstractImprecise Terrains
2009
DPP on Chordal Graphs
Frank Kammer and Torsten Tholey. The k-Disjoint Paths Problem on Chordal Graphs. WG 2009, pp. 190-201. AbstractDPP on Chordal Graphs
2008
Convex Coloring
Frank Kammer and Torsten Tholey. The Complexity of Minimum Convex Coloring. ISAAC 2008, pp. 16-27. AbstractConvex Coloring
2007
k-outerplanar
Frank Kammer. Determining the Smallest k Such That G is k-Outerplanar. ESA 2007, pp. 359-370. Abstractk-outerplanar
2006
Simultaneous Embedding
Frank Kammer. Simultaneous Embedding with Two Bends per Edge in Polynomial Area. SWAT 2006, pp. 255-267. AbstractSimultaneous Embedding


  Journals:

2016
QueryCompetitive
Frank Kammer und Torsten Tholey. Approximate tree decompositions of planar graphs in linear time. Theor. Comput. Sci. 645: 60-90 (2016).
QueryCompetitive
Thomas Erlebach, Michael Hoffmann und Frank Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci. 613: 51-64 (2016).
2015
MaxLeaf
Frank Kammer. A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem. Discrete Applied Mathematics, vol 193, pp. 126-138, 2015.
2014
Intersection Graphs
Frank Kammer, Torsten Tholey. Approximation Algorithms for Intersection Graphs. Algorithmica, vol 68(2), pp. 312-336, 2014.
2012
Sensor Cover
Chris Gray, Frank Kammer, Maarten Löffler, and Rodrigo I. Silveira. Removing local extrema from imprecise terrains. Computational Geometry, vol. 45(7), pp. 334-349, 2012.
Convex Coloring
Frank Kammer and Torsten Tholey. The Complexity of Minimum Convex Coloring. Discrete Applied Mathematics, vol. 160(6), pp. 810-833, 2012.  
2011
Sensor Cover
Thomas Erlebach, Tom Grant, and Frank Kammer. Maximising lifetime for fault-tolerant target coverage in sensor networks. Sustainable Computing 1(3): Informatics and Systems, vol. 1(3), pp. 213-225, 2011.


  Summary, Thesis, and Book Chapter:

2016
Summary
Frank Kammer. Algorithm Design under Consideration of Different Resources and a Faulty World. Summary
2010
Thesis
Frank Kammer. Treelike and Chordal Graphs: Algorithms and Generalizations. Thesis
2004
Networks
Frank Kammer and Hanjo Täubig. Connectivity. Network Analysis 2004, pp. 143-177.


  Some Talks:

Temporal Graph Exploration
Talk given at the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, July 6-10, 2015.
Temporal Graph Exploration
Space Efficient Basic Graph Algoriuthms
Talk given at the 32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany, March 4-7, 2015.
Space Efficient Basic Graph Algoriuthms
DPP on Chordal Graphs
My disputation (in german) at the University of Augsburg in 2010.
Disputation
DPP on Chordal Graphs
Talk given University of Bergen at their algorithms-seminar-series 2010.
Generalize from and to Chordal Graphs
DPP on Chordal Graphs
Talk given at the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Monpellier, France, June 24-26, 2009.
Talk DPP on Chordal Graphs
Convex Coloring
Talk given at the 19th International Symposium on Algorithms and Computation (ISAAC 2008), Gold Coast, Australia, December 15-17, 2008.
Talk Convex Coloring
k-outerplanar
Talk given at the 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, Israel, October 8-10, 2007.
Talk k-outerplanar


  Technical Reports and ArXiv.org Papers (not published at a conference or in a journal):

2009
Networks
Frank Kammer and Torsten Tholey. A Lower Bound for the Treewidth of k-Outerplanar Graphs. Uni Augsburg, Report 2009-7, 2009. treewidth of k-outer graphs
2004
Networks
Frank Kammer and Hanjo Täubig. Graph Connectivity. TU München, TUM-I0422, 2004. Graph Connectivity


  Teaching:

WS 15/16
Platzeffiziente Algorithmen (assistant to Prof. Dr. Torben Hagerup)
Repetitorium Informatik III
SS 15
Algorithmen für NP-harte Probleme (assistant to Prof. Dr. Torben Hagerup)
WS 14/15
Flüsse in Netzwerken (assistant to Prof. Dr. Torben Hagerup)
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
SS 14
Teile-und-Herrsche-Algorithmen
Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
SS 13
Einführung in die Theoretische Informatik
Algorithmen für NP-harte Probleme (assistant to Prof. Dr. Torben Hagerup)
WS 12/13
Teile-und-Herrsche-Algorithmen
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Algorithmische Geometrie (assistant to Prof. Dr. Torben Hagerup)
SS 12
Online Algorithmen (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Graphalgorithmen
WS 11/12
Teile-und-Herrsche-Algorithmen
SS 11
Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
I/O effiziente Algorithmen (assistant to Prof. Dr. Torben Hagerup)
Praktikum: NP-harte Graphprobleme
WS 10/11
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Seminar über Algorithmen und Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
SS 10 (University of Leicester, Great Britain)
Mini Course on Tree Decompositions
SS 09
Online Algorithmen (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Zeichnen von Graphen
WS 08/09
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Implementierung von Graphenalgorithmen
SS 08
Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Implementierung von Graphenalgorithmen
WS 07/08
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Algorithmische Geometrie (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Zeichnen von Graphen
SS 07
Algorithmen für NP-harte Probleme (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Visualisieren von Graphalgorithmen
WS 06/07
Informatik III (assistant to Prof. Dr. Walter Vogler)
Praktikum: Visualisieren von Graphalgorithmen
SS 06
Einführung in die Theoretische Informatik (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Zeichnen von Graphen
WS 05/06
Online Algorithmen (assistant to Prof. Dr. Torben Hagerup)
Praktikum: Zeichnen von Graphen
SS 05
Datenstrukturen (assistant to Prof. Dr. Torben Hagerup)
Einführung in die Komplexitätstheorie (assistant to Prof. Dr. Torben Hagerup)
WS 04/05
Informatik III (assistant to Prof. Dr. Torben Hagerup)
SS 04
Flüsse in Netzwerken (assistant to Prof. Dr. Torben Hagerup)
WS 03/04
Informatik III (assistant to Prof. Dr. Torben Hagerup)
Einführung in die Komplexitätstheorie (assistant to Prof. Dr. Torben Hagerup)


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