I am now Professor at TU Kaiserslautern.

Pascal Schweitzer

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
CAMPUS E1 4, Office 322
66123 Saarbrücken
Germany

Email: Get email address via email

Research Interests

The Graph Isomorphism Problem
Algorithmic and Structural Graph Theory
Algorithmic and Structural Group Theory
Online Algorithms

Publications

W. Li, H. Saidi, H. Sanchez, M. Schäf, P. Schweitzer: Detecting similar programs via the Weisfeiler-Leman graph kernel.
In Proceedings of 15th International Conference on Software Reuse, (ICSR2016) Limassol, Cyprus, 2016, to appear

S. Kiefer, P. Schweitzer: Upper bounds on the quantifier depth for graph differentiation in first order logic.
In 31th Annual ACM/IEEE Symposium on Logic in Computer Science, (LICS2016) New York City, USA, 2016. to appear

M. Grohe, P. Schweitzer: Computing with tangles
SIAM Journal on Discrete Mathematics, 2016, to appear.

M. Elberfeld, P. Schweitzer: Canonizing graphs of bounded tree width in logspace.
In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS2016), Orléans, France, 2016

T. Hartnick, P. Schweitzer: On quasioutomorphism groups of free groups and their transitivity properties
Journal of Algebra, 450:242-281, 2016

S. Kiefer, P. Schweitzer, E. Selman: Graphs identified by logics with counting.
In Proceedings of Mathematical Foundations of Computer Science 2015 - 40th International Symposium (MFCS2015) Milano, Italy, 2015

P. Eades, S. Hong, Naoki Katoh, Giuseppe Liotta, P. Schweitzer, Yusuke Suzuki: A linear-time algorithm for testing outer-1-planarity
Algorithmica, 72(4):1033–1054, 2015

M. Grohe, P. Schweitzer: Isomorphism testing for graphs of bounded rank width.
In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS2015) Berkeley, California, 2015

P. Schweitzer: Towards an Isomorphism Dichotomy for Hereditary Graph Classes
In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS2015), Munich, Germany, 2015

M. Grohe, P. Schweitzer: Computing with Tangles
In Proceedings of ACM Symposium on Theory of Computing (STOC2015) Portland, USA, 2015

R. Belmonte, Y. Otachi, P. Schweitzer: Induced Minor Free Graphs: Isomorphism and Clique-width
In Proceedings of Workshop on Graph Theoretic Concepts in Computer (WG2015) Munich, Germany , 2015

Y. Otachi, P. Schweitzer: Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
In Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT2014) Copenhagen, Denmark , 2014

Brendan D. McKay, P. Schweitzer, P. Schweitzer: Competition Numbers, Quasi-line Graphs, and Holes
SIAM Journal on Discrete Mathematics, 28(1):77–91, 2014

T. Asano, T. Izumi, M. Kiyomi, M. Konagaya, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui, R. Uehara: Depth-First Search Using O(n) Bits
In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC2014) Jeonju, Korea, 2014

Brendan D. McKay, P. Schweitzer: Switching reconstruction of digraphs
Journal of Graph Theory, 76(4):279–296, 2014

P. Schweitzer: On zero divisors with small support in group rings of torsion-free groups
Journal of Group Theory, 16(5):619–792, 2013

Y. Otachi, P. Schweitzer: Isomorphism on subgraph-closed graph classes: A complexity dichotomy and intermediate graph classes
In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC2013) Hong Kong, 2013

P. Schweitzer: Iterated open neighborhood graphs and generalizations
Discrete Applied Mathematics, 161(10-11):1598–1609, 2013

P. Eades, S. Hong, Naoki Katoh, Giuseppe Liotta, P. Schweitzer, Yusuke Suzuki: A linear-time algorithm for testing outer-1-planarity
In Proceedings of the 21st International Symposium on Graph Drawing (GD2013) Bordeaux, France, 2013

W. Liang, P. Schweitzer, Z. Xu: Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink
IEEE Transactions on Computers, 62(10):1932–1944, 2013

S. Angelopoulos, P. Schweitzer: Paging and list update under bijective analysis
Journal of the ACM, 60(2):7, 2013

P. Eades, S. Hong, Naoki Katoh, Giuseppe Liotta, P. Schweitzer, Yusuke Suzuki: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
Theoretical Computer Science, 513:65–76, 2013

N. Megow, K. Mehlhorn, P. Schweitzer: Online Graph Exploration: New Results on Old and New Algorithms
Theoretical Computer Science, 463:62-72, 2012

S. Kratsch, P. Schweitzer: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
In Proceedings of Workshop on Graph Theoretic Concepts in Computer (WG2012) Jerusalem, Isreal, 2012 (arXiv)

P. Eades, S. Hong, Naoki Katoh, Giuseppe Liotta, P. Schweitzer, Yusuke Suzuki: Testing maximal 1-planarity of graphs with a rotation system in linear time - (extended abstract)
In Proceedings of the 20th International Symposium on Graph Drawing (GD2012) Redmond, USA, 2012
(A refined version appeared in the journal Theoretical Computer Science, see above).

C. Bertolini, M. Schäf, P. Schweitzer: Infeasible Code Detection
In Proceedings of Verified Software: Theories, Tools and Experiments (VSTTE2012) Philadelphia, USA, 2012

E. Alkassar, S. Böhme, K. Mehlhorn, C. Rizkallah, P. Schweitzer: An Introduction to Certifying Algorithms
it - Information Technology, 53(6):287-293, 2011 (pdf)

P. Schweitzer: Isomorphism of (mis)labeled graphs
In Proceedings of the 19th Annual European Symposium on Algorithms (ESA2011) Saarbrücken, Germany, 2011 (pdf)

N. Shervashidze, P. Schweitzer, E.J. van Leeuwen, K. Mehlhorn, K.M. Borgwardt: Weisfeiler-Lehman Graph Kernels
Journal of Machine Learning Research, 12(Sep):2539−2561, 2011 (pdf)

N. Megow, K. Mehlhorn, P. Schweitzer: Online Graph Exploration: New Results on Old and New Algorithms
In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP2011), Zürich, Switzerland, 2011 (pdf)
(A refined version appeared in the journal Theoretical Computer Science, see above).

R. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer: Certifying Algorithms
Computer Science Review, 5(2):119-161, 2011 (pdf)

K. Mehlhorn, P. Schweitzer: Progress on certifying algorithms
In Proceedings of Frontiers of Algorithmics (FAW2010), Wuhan, China (pdf)

P. Schweitzer, P. Schweitzer: Connecting face hitting sets in planar graphs
Information Processing Letters, 111(1):11-15, 2010 (pdf,ps)

S. Kratsch, P. Schweitzer: Isomorphism for graphs of bounded feedback vertex set number
In Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT2010) Bergen, Norway, June 2010 (pdf,ps)

M. Rusinov, P. Schweitzer: Homomorphism-Homogeneous Graphs
Journal of Graph Theory 65(3):253–262, 2010 (pdf,ps)

S. Angelopoulos, P. Schweitzer: Paging and List Update under Bijective Analysis
In Proceedings of Symposium on Discrete Algorithms (SODA09), New York, New York, USA (pdf,ps)
(A refined version appeared in the Journal of the ACM, see above).

P. Schweitzer: Using the Incompressibility Method to obtain Local Lemma results for Ramsey-type Problems
Information Processing Letters, 109(4):229-232, 2009 (pdf,ps)

P. Cameron, D.Johannsen, T. Prellberg, P. Schweitzer: Counting Defective Parking Functions
Electronic Journal of Combinatorics, 15(1):R92, July 2008 (pdf,ps)

M. Kutz, P. Schweitzer: ScrewBox: a Randomized Certifying Graph Non-Isomorphism Algorithm.
In Proceedings of Workshop on Algorithm Engineering and Experiments (Alenex07), New Orleans, Lousiana, USA. (pdf,ps)

J. Lehnert, P. Schweitzer: The co-word problem for the Higman-Thompson group is context-free
Bulletin of the London Mathematical Society, 39(2):235-241, 2007; doi:10.1112/blms/bdl043 (Abstract ,html, pdf)

Appendix to
R. Bieri: Deficiency and the geometric invariants of a group (with an appendix by Pascal Schweitzer)
Journal of Pure and Applied Algebra, 208(3):951-959, March 2007, Pages 951-959

PhD Thesis

Phd thesis: Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers. (pdf)

Teaching

Algorithms COMP4600 in Ss 2011
Algorithms COMP4600 in Ss 2010
Algorithms COMP3600/COMP6466 in Ss 2010
Assistant to Graph Theory lecture in Ws 06/07 given by Benjamin Doerr and Martin Kutz.

Academic Appointments

January 2014 - present:
Juniorprofessor at RWTH Aachen University
January 2012 - December 2013
Laureate of the European Post-Doc Institute (EPDI)
January 2013 - December 2013
Postdoctoral Fellowship at the Forschungsinstitut für Mathematik at ETH Zürich (in the course of EPDI Laureateship)
Juli 2012 - January 2013:
JSPS Postdoctoral Fellowship at the Japan Advanced Institute of Science and Technology (in the course of EPDI Laureateship)
January 2012 - May 2012:
Fellowship Grant at Institut Mittag-Leffler (in the course of EPDI Laureateship)
June 2010 - January 2012
Visting Fellow at the Australian National University founded by an AFR PostDoc Grant of the Fonds National de la Recherche of Luxembourg
July 2009 - June 2010:
PostDoc at the Max-Planck-Institut für Informatik

Education

March 2006 - July 2009:
Ph. D. student in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institut für Informatik
Title of PhD Thesis: Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers. (supervisor: Prof. Dr. Kurt Mehlhorn) (pdf)
October 2002 - Dezember 2005:
Studies in Mathematics at the Johann Wolfgang Goethe University of Frankfurt
Title of Master Thesis (Diplomarbeit): Novikov Completions and their Application to the Geometric Invariant. (supervisor: Prof. Dr. Robert Bieri) (pdf in German )
October 2001 - October 2002:
Studies in Mathematics at the Fernuniversität Hagen
June 2001:
Abitur at the Otto-Hahn-Gymnasium Saarbrücken

Private

Hobbies

Volleyball, Cycling, Snowboarding, Fruit, Diving