# Publications of Tobias Friedrich

The following listing contains all publications of Prof. Dr. Tobias Friedrich. Further publications of the research group can be found on the current list of publications and the complete list of publications. Further individual listings are available externally on DBLP and Google Scholar or locally as PDF.

You can view all publications of the current members of the Algorithm Engineering group. For other listings, please see:

- years: 2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010
- researchers: Prof. Dr. Tobias Friedrich, Dr. Thomas Bläsius, Dr. Katrin Casel, Dr. Sarel Cohen, Dr. Ágnes Cseh, Dr. Andreas Göbel, Dr. Davis Issac, Dr. Timo Kötzing, Dr. Martin Krejca, Dr. Nikhil Kumar, Dr. Pascal Lenzner
- PhD students: Vanja Doskoč, Ziena Elijazyfer, Philipp Fischbeck, Maximilian Katzmann, Ardalan Khazraei, Simon Krogmann, Gregor Lagodzinski, Anna Melnichenko, Louise Molitor, Stefan Neubert, Francesco Quinzan, Ralf Rothenberger, Martin Schirneck, Karen Seidel, Christopher Weyand
- theory conferences: ICALP, MFCS, SAGT, STACS, STOC, WINE

algorithm conferences: ALENEX, ESA, GD, ISAAC, SODA, SPAA, SWAT, WAW - artificial intelligence conferences: AAAI, AAMAS, ALT, COLT, ECAI, ICAPS, IJCAI, SAT

evolutionary computation conferences: CEC, EMO, EvoCOP, FOGA, GECCO, PPSN

2021 [ to top ]

- The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021

2020 [ to top ]

- Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2020: 3117-3123
- Greed is Good for Deterministic Scale-Free Networks. Algorithmica 2020: 3338–3389
- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
- Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
- Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Theoretical Computer Science 2020: 3-19
- A Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1--10:14
- Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020: 435-442
- The Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15
- Fair Tree Connection Games with Topology-Dependent Edge Cost. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020
- Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation. International Conference on Neural Information Processing (ICONIP) 2020: 592-604
- Flow-Based Network Creation Games. International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139-145
- Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1-25:14

2019 [ to top ]

- Routing for On-Street Parking Search using Probabilistic Data. AI Communications 2019: 113-124
- Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2019: 828-857
- Island Models Meet Rumor Spreading. Algorithmica 2019: 886-915
- Quasi-random Image Transition and Animation. Australian Journal of Intelligent Information Processing Systems 2019: 10-18
- Unbiasedness of Estimation-of-Distribution Algorithms. Theoretical Computer Science 2019: 46-59
- Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2272-2279
- Pareto Optimization for Subset Selection with Dynamic Cost Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2354-2361
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143
- Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:2-21:14EATCS Best Paper Award
- The Satisfiability Threshold for Non-Uniform Random 2-SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1-61:14
- Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem. International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541-554
- Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151-6155
- Geometric Network Creation Games. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323-332
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
- On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117-134
- Understanding the Effectiveness of Data Reduction in Public Transportation Networks. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87-101
- Convergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019: 156-170
- FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. 2019ACM.Editorship
- Theory of Randomized Optimization Heuristics. Dagstuhl Reports 2019: 61-94

2018 [ to top ]

- Cliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
- De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica 2018: 3397–3427
- On the diameter of hyperbolic random graphs. SIAM Journal on Discrete Mathematics 2018: 1314-1334
- Unbounded Discrepancy of Deterministic Random Walks on Grids. SIAM Journal on Discrete Mathematics 2018: 2441-2452
- Escaping Local Optima Using Crossover with Emergent Diversity. Transactions on Evolutionary Computation 2018: 484-497
- Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
- Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators. Genetic and Evolutionary Computation Conference (GECCO) 2018: 293-300
- Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Genetic and Evolutionary Computation Conference (GECCO) 2018: 301-308
- Randomized Greedy Algorithms for Covering Problems. Genetic and Evolutionary Computation Conference (GECCO) 2018: 309-315
- Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
- Heavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization. Parallel Problem Solving From Nature (PPSN) 2018: 134-145
- Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273-291Best Paper Award
- Memory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
- Towards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114

2017 [ to top ]

- Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 2017: 515-536
- The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise. Transactions on Evolutionary Computation 2017: 477-490
- A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. Conference on Artificial Intelligence (AAAI) 2017: 801-807
- Phase Transitions for Scale-Free SAT Formulas. Conference on Artificial Intelligence (AAAI) 2017: 3893-3899
- What's Hot in Evolutionary Computation. Conference on Artificial Intelligence (AAAI) 2017: 5064-5066
- Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization. Australasian Conference on Artificial Intelligence (AUSAI) 2017: 131-143
- Improving local search in a minimum vertex cover solver for classes of networks. Congress on Evolutionary Computation (CEC) 2017: 1704-1711
- Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA) 2017: 37:1-37:15
- Resampling vs Recombination: a Statistical Run Time Estimation. Foundations of Genetic Algorithms (FOGA) 2017: 25-35
- On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms. Foundations of Genetic Algorithms (FOGA) 2017: 37-44
- Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Foundations of Genetic Algorithms (FOGA) 2017: 45-54
- Approximating Optimization Problems using EAs on Scale-Free Networks. Genetic and Evolutionary Computation Conference (GECCO) 2017: 235-242
- Analyzing Search Heuristics with Differential Equations. Genetic and Evolutionary Computation Conference (GECCO) 2017: 313-314
- Island Models Meet Rumor Spreading. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1359-1366
- Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2017: 1407-1414
- Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Algorithmic Game Theory (SAGT) 2017: 199-211
- Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2017: 321-323

2016 [ to top ]

- Robustness of Ant Colony Optimization to Noise. Evolutionary Computation 2016: 237-254
- Probabilistic Routing for On-Street Parking Search. European Symposium on Algorithms (ESA) 2016: 6:1-6:13
- Hyperbolic Random Graphs: Separators and Treewidth. European Symposium on Algorithms (ESA) 2016: 15:1-15:16
- Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:1-16:18EATCS Best Paper Award
- Greed is Good for Deterministic Scale-Free Networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1-33:15
- Ant Colony Optimization Beats Resampling on Noisy Functions. Genetic and Evolutionary Computation Conference (GECCO) 2016: 3-4
- The Benefit of Recombination in Noisy Evolutionary Search. Genetic and Evolutionary Computation Conference (GECCO) 2016: 161-162
- Escaping Local Optima with Diversity Mechanisms and Crossover. Genetic and Evolutionary Computation Conference (GECCO) 2016: 645-652
- Fast Building Block Assembly by Majority Vote Crossover. Genetic and Evolutionary Computation Conference (GECCO) 2016: 661-668
- EDAs cannot be Balanced and Stable. Genetic and Evolutionary Computation Conference (GECCO) 2016: 1139-1146
- The Parameterized Complexity of Dependency Detection in Relational Databases. International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1-6:13
- Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms. Symposium on Mathematical Foundations of Computer Science (MFCS) 2016: 4:1-4:3Invited Talk
- Fixed-Parameter Single Objective Search Heuristics for Minimum Vertex Cover. Parallel Problem Solving From Nature (PPSN) 2016: 740-750
- Graceful Scaling on Uniform versus Steep-Tailed Noise. Parallel Problem Solving From Nature (PPSN) 2016: 761-770
- On the Robustness of Evolving Populations. Parallel Problem Solving From Nature (PPSN) 2016: 771-781
- Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms. Parallel Problem Solving From Nature (PPSN) 2016: 890-900
- Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20 - 24, 2016. 2016ACM.Editorship
- Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20-24, 2016, Companion Material Proceedings. 2016ACM.Editorship

2015 [ to top ]

- Seeding the initial population of multi-objective evolutionary algorithms: A computational study. Applied Soft Computing 2015: 223-230
- Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics 2015: 130-138
- Efficient optimization of many objectives by approximation-guided evolution. European Journal of Operational Research 2015: 465-479
- Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point. Evolutionary Computation 2015: 131-159
- Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms. Evolutionary Computation 2015: 543-558
- Randomized diffusion for indivisible loads. Journal of Computer and System Sciences 2015: 159-185
- On the kernel size of clique cover reductions for random intersection graphs. Journal of Discrete Algorithms 2015: 128-136
- Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology 2015: 28-43
- Genetic and Evolutionary Computation. Theoretical Computer Science 2015: 1-2
- On the average-case complexity of parameterized clique. Theoretical Computer Science 2015: 18-29
- Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator. Congress on Evolutionary Computation (CEC) 2015: 970-977
- Robustness of Ant Colony Optimization to Noise. Genetic and Evolutionary Computation Conference (GECCO) 2015: 17-24Best-Paper Award (ACO/SI Track)
- Ultra-Fast Load Balancing on Scale-Free Networks. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516-527
- On the Diameter of Hyperbolic Random Graphs. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 614-625
- Cliques in Hyperbolic Random Graphs. International Conference on Computer Communications (INFOCOM) 2015: 1544-1552
- The Benefit of Recombination in Noisy Evolutionary Search. International Symposium of Algorithms and Computation (ISAAC) 2015: 140-150
- Unbounded Discrepancy of Deterministic Random Walks on Grids. International Symposium on Algorithms and Computation (ISAAC) 2015: 212-222

2014 [ to top ]

- Genetic and Evolutionary Computation. Theoretical Computer Science 2014: 1
- Quasirandom Rumor Spreading. Transactions on Algorithms 2014: 9:1-9:35
- Convergence of Hypervolume-Based Archiving Algorithms. Transactions on Evolutionary Computation 2014: 643-657
- De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. European Symposium on Algorithms (ESA) 2014: 197-208
- Two-dimensional subset selection for hypervolume and epsilon-indicator. Genetic and Evolutionary Computation Conference (GECCO) 2014: 589-596
- Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. Parallel Problem Solving from Nature (PPSN) 2014: 518-527
- Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms. Parallel Problem Solving from Nature (PPSN) 2014: 922-931Nominated for Best Paper Award

2013 [ to top ]

- Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. Algorithmica 2013: 65-88
- Speeding up many-objective optimization by Monte Carlo approximations. Artificial Intelligence 2013: 22-29
- Approximation quality of the hypervolume indicator. Artificial Intelligence 2013: 265-290
- Weighted preferences in evolutionary multi-objective optimization. Machine Learning and Cybernetics 2013: 139-148
- Fast simulation of large-scale growth models. Random Structures and Algorithms 2013: 185-213
- Predicting the Energy Output of Wind Farms Based on Weather Data: Important Variables and their Correlation. Renewable Energy 2013: 236-243
- Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable. Theoretical Computer Science 2013: 81-89
- Efficient parent selection for Approximation-Guided Evolutionary multi-objective optimization. Congress on Evolutionary Computation (CEC) 2013: 1846-1853
- Parameterized average-case complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO) 2013: 575-582Nominated for Best Paper Award (EMO Track)
- Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. International Colloquium on Automata, Languages and Programming (ICALP) 2013: 13-24
- Exact and Efficient Generation of Geometric Random Variates and Random Graphs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 267-278

2012 [ to top ]

- Why rumors spread so quickly in social networks. Communications of the ACM 2012: 70-75
- Efficient Key Pathway Mining: Combining Networks and OMICS Data. Integrative Biology 2012: 756-764
- Quasirandom Load Balancing. SIAM Journal on Computing 2012: 747-771
- Convergence of Set-Based Multi-Objective Optimization, Indicators and Deteriorative Cycles. Theoretical Computer Science 2012: 2-17
- Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theoretical Computer Science 2012: 104-116
- Efficient Algorithms for Extracting Biological Key Pathways with Global Constraints. Genetic and Evolutionary Computation Conference (GECCO) 2012: 169-176