Pascal Schweitzer

CoRR, 2024

Computational complexity of the Weisfeiler-Leman dimension.

[BibT_eX]

[DOI]

Simon Raßmann

CoRR, 2024

2023

A Faster Isomorphism Test for Graphs of Small Degree.

[BibT_eX]

[DOI]

SIAM J. Comput., December, 2023

Engineering a Preprocessor for Symmetry Detection.

[BibT_eX]

[DOI]

Julian Stieß

Proceedings of the 21st International Symposium on Experimental Algorithms, 2023

Algorithms Transcending the SAT-Symmetry Interface.

[BibT_eX]

[DOI]

Mate Soos

Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing, 2023

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Exploration of Graphs with Excluded Minors.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Graphs Identified by Logics with Counting.

[BibT_eX]

[DOI]

Sandra Kiefer

Erkal Selman

ACM Trans. Comput. Log., 2022

Choiceless Polynomial Time with Witnessed Symmetric Choice.

[BibT_eX]

[DOI]

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension.

[BibT_eX]

[DOI]

Jendrik Brachter

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Trainability for Universal GNNs Through Surgical Randomness.

[BibT_eX]

[DOI]

CoRR, 2021

Technical perspective: A logical step toward the graph isomorphism problem.

[BibT_eX]

[DOI]

Commun. ACM, 2021

Resolution with Symmetry Rule Applied to Linear Equations.

[BibT_eX]

[DOI]

Constantin Seebach

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Deep Weisfeiler Leman.

[BibT_eX]

[DOI]

Daniel Wiebking

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Characterization of Individualization-Refinement Trees.

[BibT_eX]

[DOI]

Jendrik Brachter

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case.

[BibT_eX]

[DOI]

Florian Wetzels

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Parallel Computation of Combinatorial Symmetries.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

Engineering a Fast Probabilistic Isomorphism Test.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Algorithm Engineering and Experiments, 2021

2020

An Improved Isomorphism Test for Bounded-tree-width Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Space-Efficient Algorithms for Longest Increasing Subsequence.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

Automorphism groups of graphs of bounded Hadwiger number.

[BibT_eX]

[DOI]

Daniel Wiebking

CoRR, 2020

The graph isomorphism problem.

[BibT_eX]

[DOI]

Commun. ACM, 2020

Stochastic Dominance and the Bijective Ratio of Online Algorithms.

[BibT_eX]

[DOI]

Spyros Angelopoulos

Marc P. Renault

Algorithmica, 2020

On the Weisfeiler-Leman Dimension of Finite Groups.

[BibT_eX]

[DOI]

Jendrik Brachter

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

2019

Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic.

[BibT_eX]

[DOI]

Sandra Kiefer

Log. Methods Comput. Sci., 2019

The Weisfeiler-Leman Dimension of Planar Graphs Is at Most 3.

[BibT_eX]

[DOI]

Sandra Kiefer

Ilia Ponomarenko

J. ACM, 2019

A unifying method for the design of algorithms canonizing combinatorial objects.

[BibT_eX]

[DOI]

Daniel Wiebking

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm.

[BibT_eX]

[DOI]

Ilia Ponomarenko

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2018

Towards faster isomorphism tests for bounded-degree graphs.

[BibT_eX]

[DOI]

CoRR, 2018

Induced Minor Free Graphs: Isomorphism and Clique-Width.

[BibT_eX]

[DOI]

Rémy Belmonte

Yota Otachi

Algorithmica, 2018

An exponential lower bound for individualization-refinement algorithms for graph isomorphism.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Canonizing Graphs of Bounded Tree Width in Logspace.

[BibT_eX]

[DOI]

Michael Elberfeld

ACM Trans. Comput. Theory, 2017

Towards an Isomorphism Dichotomy for Hereditary Graph Classes.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Minimal asymmetric graphs.

[BibT_eX]

[DOI]

Patrick Schweitzer

J. Comb. Theory, Ser. B, 2017

Graph isomorphism for graph classes characterized by two forbidden induced subgraphs.

[BibT_eX]

[DOI]

Stefan Kratsch

Discret. Appl. Math., 2017

A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Benchmark Graphs for Practical Graph Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Computing with Tangles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

Detecting Similar Programs via The Weisfeiler-Leman Graph Kernel.

[BibT_eX]

[DOI]

Proceedings of the Software Reuse: Bridging with Social-Awareness, 2016

2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

A Linear-Time Algorithm for Testing Outer-1-Planarity.

[BibT_eX]

[DOI]

Algorithmica, 2015

Isomorphism Testing for Graphs of Bounded Rank Width.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Competition Numbers, Quasi-line Graphs, and Holes.

[BibT_eX]

[DOI]

Brendan D. McKay

Patrick Schweitzer

SIAM J. Discret. Math., 2014

Switching Reconstruction of Digraphs.

[BibT_eX]

[DOI]

Brendan D. McKay

J. Graph Theory, 2014

Reduction Techniques for Graph Isomorphism in the Context of Width Parameters.

[BibT_eX]

[DOI]

Yota Otachi

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Depth-First Search Using O(n) Bits.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Approximation Algorithms for Capacitated Minimum Forest Problems in Wireless Sensor Networks with a Mobile Sink.

[BibT_eX]

[DOI]

Weifa Liang

Zichuan Xu

IEEE Trans. Computers, 2013

Paging and list update under bijective analysis.

[BibT_eX]

[DOI]

Spyros Angelopoulos

J. ACM, 2013

Iterated open neighborhood graphs and generalizations.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes.

[BibT_eX]

[DOI]

Yota Otachi

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012

Online graph exploration: New results on old and new algorithms.

[BibT_eX]

[DOI]

Nicole Megow

Kurt Mehlhorn

Theor. Comput. Sci., 2012

On Zero Divisors with Small Support in Group Rings of Torsion-Free Groups

[BibT_eX]

[DOI]

CoRR, 2012

Infeasible Code Detection.

[BibT_eX]

[DOI]

Cristiano Bertolini

Martin Schäf

Proceedings of the Verified Software: Theories, Tools, Experiments, 2012

Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 20th International Symposium, 2012

2011

Weisfeiler-Lehman Graph Kernels.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2011

An Introduction to Certifying Algorithms.

[BibT_eX]

[DOI]

it Inf. Technol., 2011

Certifying algorithms.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2011

Isomorphism of (mis)Labeled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

Homomorphism-homogeneous graphs.

[BibT_eX]

[DOI]

Momchil Rusinov

J. Graph Theory, 2010

Connecting face hitting sets in planar graphs.

[BibT_eX]

[DOI]

Patrick Schweitzer

Inf. Process. Lett., 2010

Isomorphism for Graphs of Bounded Feedback Vertex Set Number.

[BibT_eX]

[DOI]

Stefan Kratsch

Proceedings of the Algorithm Theory, 2010

Progress on Certifying Algorithms.

[BibT_eX]

[DOI]

Kurt Mehlhorn

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009

Using the incompressibility method to obtain local lemma results for Ramsey-type problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

2008

Counting Defective Parking Functions.

[BibT_eX]

[DOI]

Electron. J. Comb., 2008

2007

ScrewBox: a Randomized Certifying Graph-Non-Isomorphism Algorithm.

[BibT_eX]

[DOI]

Martin Kutz