Thomas Bläsius
Head of the Scalable Algorithms Group
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics
| thomas.blaesius@kit.edu | |
| office | room 309, Computer Science building 50.34 |
| office hours | by appointment |
Research
My research is centered around the question of why algorithms often perform better in practice than the theoretical run time bounds predict. I attempt to shrink this theory-practice gap by taking properties regularly observed in real-world instances into account rather than analyzing the worst case. In this context, my research intersects with multiple other areas in the field of algorithmics, including the following:
- graph algorithms
- computational geometry
- probabilistic methods (e.g., average case analysis)
- propositional satisfiability
- algorithm engineering
- network science
Publications
2024
On the External Validity of Average-case Analyses of Graph Algorithms.
ACM Transactions on Algorithms (TALG) 2024
2023
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry.
Algorithmica 2023
The impact of geometry on monochrome regions in the flip Schelling process.
Computational Geometry 2023
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Theory of Computing Systems 2023
The impact of heterogeneity and geometry on the proof complexity of random satisfiability.
Random Structures and Algorithms 2023
Synchronized Planarity with Applications to Constrained Planarity Problems.
ACM Transactions on Algorithms (TALG) 2023
Dynamic Flows with Time-Dependent Capacities.
International/Italian Conference on Algorithms and Complexity (CIAC) 2023
On the Giant Component of Geometric Inhomogeneous Random Graphs.
European Symposium on Algorithms (ESA) 2023
An Efficient Algorithm for Power Dominating Set.
European Symposium on Algorithms (ESA) 2023
Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks.
International Workshop on Combinatorial Algorithms (IWOCA) 2023
Strongly Hyperbolic Unit Disk Graphs.
Symposium on Theoretical Aspects of Computer Science (STACS) 2023
Partitioning the Bags of a Tree Decomposition into Cliques.
Symposium on Experimental and Efficient Algorithms (SEA) 2023
2022
Efficiently enumerating hitting sets of hypergraphs arising in data profiling.
Journal of Computer and System Sciences (JCSS) 2022
Efficiently generating geometric inhomogeneous and hyperbolic random graphs.
Network Science 2022
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
ACM Transactions on Algorithms (TALG) 2022
The complexity of dependency detection and discovery in relational databases.
Theoretical Computer Science 2022
An Efficient Branch-and-Bound Solver for Hitting Set.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2022
On the External Validity of Average-Case Analyses of Graph Algorithms.
European Symposium on Algorithms (ESA) 2022
A Branch-And-Bound Algorithm for Cluster Editing.
Symposium on Experimental and Efficient Algorithms (SEA) 2022
2021
Synchronized Planarity with Applications to Constrained Planarity Problems.
European Symposium on Algorithms (ESA) 2021
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry.
European Symposium on Algorithms (ESA) 2021
Efficiently Computing Maximum Flows in Scale-Free Networks.
European Symposium on Algorithms (ESA) 2021
The Impact of Geometry on Monochrome Regions in the Flip Schelling Process.
International Symposium on Algorithms and Computation (ISAAC) 2021
PACE Solver Description: The KaPoCE Exact Cluster Editing Algorithm.
International Symposium on Parameterized and Exact Computation (IPEC) 2021
PACE Solver Description: KaPoCE: A Heuristic Cluster Editing Algorithm.
International Symposium on Parameterized and Exact Computation (IPEC) 2021
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021
Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane.
Symposium on Experimental and Efficient Algorithms (SEA) 2021
2020
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
ACM Journal of Experimental Algorithmics (JEA) 2020
Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery.
Proceedings of the VLDB Endowment 2020
A Strategic Routing Framework and Algorithms for Computing Alternative Paths.
Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS) 2020
The Minimization of Random Hypergraphs.
European Symposium on Algorithms (ESA) 2020
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Symposium on Theoretical Aspects of Computer Science (STACS) 2020
2019
How to Draw a Planarization.
Journal of Graph Algorithms and Applications 2019
Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2019
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
European Symposium on Algorithms (ESA) 2019
On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition.
International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS) 2019
Understanding the Effectiveness of Data Reduction in Public Transportation Networks.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2019
2018
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices.
Algorithmica 2018
Cliques in Hyperbolic Random Graphs.
Algorithmica 2018
Local and union boxicity.
Discrete Mathematics 2018
Scalable exact visualization of isocontours in road networks via minimum-link paths.
Journal of Computational Geometry (JoCG) 2018
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane.
IEEE/ACM Transactions on Networking (TON) 2018
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2018
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
International Colloquium on Automata, Languages and Programming (ICALP) 2018
Memory-Restricted Routing with Tiled Map Data.
IEEE International Conference on Systems, Man and Cybernetics (SMC) 2018
Towards a Systematic Evaluation of Generative Network Models.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2018
2017
TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers.
International Conference on Human Factors in Computing Systems (CHI) 2017
How to Draw a Planarization.
Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) 2017
Demonstrating TrussFab's Editor: Designing Sturdy Large-Scale Structures.
ACM Symposium on User Interface Software and Technology (UIST) 2017
2016
Orthogonal graph drawing with inflexible edges.
Computational Geometry 2016
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
ACM Transactions on Algorithms (TALG) 2016
Optimal Orthogonal Graph Drawing with Convex Bend Costs.
ACM Transactions on Algorithms (TALG) 2016
A new perspective on clustered planarity as a combinatorial embedding problem.
Theoretical Computer Science 2016
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths.
European Symposium on Algorithms (ESA) 2016
Hyperbolic Random Graphs: Separators and Treewidth.
European Symposium on Algorithms (ESA) 2016
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane.
European Symposium on Algorithms (ESA) 2016
The Parameterized Complexity of Dependency Detection in Relational Databases.
International Symposium on Parameterized and Exact Computation (IPEC) 2016
2015
New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity.
Karlsruhe Institute of Technology 2015
Disconnectivity and relative positions in simultaneous embeddings.
Computational Geometry 2015
Orthogonal Graph Drawing with Inflexible Edges.
International/Italian Conference on Algorithms and Complexity (CIAC) 2015
Pixel and Voxel Representations of Graphs.
International Symposium Graph Drawing and Network Visualization (GD) 2015
Neue Methoden für klassische Grapheinbettungsprobleme - Orthogonale Zeichnungen & bedingte Planarität.
Ausgezeichnete Informatikdissertationen 2015
2014
Orthogonal Graph Drawing with Flexibility Constraints.
Algorithmica 2014
Testing Mutual duality of Planar graphs.
International Journal of Computational Geometry and Applications 2014
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model.
European Symposium on Algorithms (ESA) 2014
A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.
International Symposium Graph Drawing and Network Visualization (GD) 2014
2013
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices.
International Symposium Graph Drawing and Network Visualization (GD) 2013
Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings.
International Symposium Graph Drawing and Network Visualization (GD) 2013
Optimal Orthogonal Graph Drawing with Convex Bend Costs.
International Colloquium on Automata, Languages and Programming (ICALP) 2013
Testing Mutual Duality of Planar Graphs.
International Symposium on Algorithms and Computation (ISAAC) 2013
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2013
Simultaneous Embedding of Planar Graphs.
Handbook of Graph Drawing and Visualization 2013
2012
Disconnectivity and Relative Positions in Simultaneous Embeddings.
International Symposium Graph Drawing and Network Visualization (GD) 2012
2010
Orthogonal Graph Drawing with Flexibility Constraints.
International Symposium Graph Drawing and Network Visualization (GD) 2010