Publikationen


  • M. Grohe, D. Neuen, P. Schweitzer: A Faster Isomorphism Test for Graphs of Small Degree.
    In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science October 7-9 (FOCS2018) Paris, France, 2018. to appear (arXiv)
  • D. Neuen, P. Schweitzer: An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism.
    In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing June 25-29 (STOC2018) Los Angeles, USA, 2018. to appear (arXiv)
  • M. Grohe, D. Neuen, P. Schweitzer, D. Wiebking: An improved isomorphism test for bounded-tree-width graphs.
    In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming July 9-13 (ICALP2018) Prague, Czech Republic, 2018. to appear (arXiv)
  • M. Kiyomi, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui: Space-efficient algorithms for longest increasing subsequence.
    In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS2018) Caen, France, 2018
  • R. Belmonte, Y. Otachi, P. Schweitzer: Induced Minor Free Graphs: Isomorphism and Clique-width
    Algorithmica, 2018.
  • P. Schweitzer, P. Schweitzer: Minimal Asymmetric Graphs.
    Journal of Combinatorial Theory, Series B, 127:215–227, 2017
  • D. Neuen, P. Schweitzer: Benchmark graphs for practical graph isomorphism
    In Proceedings of the 25th Annual European Symposium on Algorithms (ESA2017) Vienna, Austria, 2017
  • P. Schweitzer: Towards an Isomorphism Dichotomy for Hereditary Graph Classes.
    Theory of Computing Systems, 61(4):1084–1127, 2017
  • P. Schweitzer: A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry.
    In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP2017), Warsaw, Poland, 2017
  • S. Kratsch, P. Schweitzer: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs.
    Discrete Applied Mathematics, 216:240–253, 2017
  • S. Kiefer, I. Ponomarenko, P. Schweitzer: The Weisfeiler-Leman dimension of planar graphs is at most 3.
    In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, (LICS2017) Reykjavik, Iceland, 2017
  • M. Elberfeld, P. Schweitzer: Canonizing graphs of bounded tree width in logspace.
    ACM Transactions on Computation Theory, 9(3):12:1–12:29, 2017.
  • 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
  • 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.
  • M. Grohe, P. Schweitzer: Computing with tangles
    SIAM Journal on Discrete Mathematics, 2016.
  • 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 (A refined version appeared in the journal Transactions on Computation Theory, see above)
  • 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 (FOCS), 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 (STACS), Munich, Germany, 2015 (A refined version appeared in the journal Theory of Computing Systems, see above)
  • M. Grohe, P. Schweitzer: Computing with Tangles
    In Proceedings of ACM Symposium on Theory of Computing (STOC) Portland, USA, 2015 (A refined version appeared in the SIAM Journal on Discrete Mathematics, see above)
  • 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 (A refined version appeared in the journal Algorithmica, see above)
  • 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) (A refined version appeared in the journal Discrete Applied Mathematics, see above)
  • 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)