Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

All publications in 2019

The following listing contains all publications of the current members of the Algorithm Engineering group in 2019.


Conference Publications

2019

  • Hadwiger's conjecture for... - Download
    Issac, Davis; Chandran, L. Sunil; Zhou, Sanming Hadwiger’s conjecture for squares of 2-treesEuropean Journal of Combinatorics 2019: 159–174
     
  • Routing for On-Street Par... - Download
    Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin Routing for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124
     
  • Solving Problems with Unk... - Download
    Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Solving Problems with Unknown Solution Length at Almost No Extra CostAlgorithmica 2019: 703–748
     
  • Reoptimization Time Analy... - Download
    Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica 2019: 828–857
     
  • Island Models Meet Rumor ... - Download
    Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin Island Models Meet Rumor SpreadingAlgorithmica 2019: 886–915
     
  • New and Simple Algorithms... - Download
    Cseh, Ágnes; Matuschke, Jannik New and Simple Algorithms for Stable Flow ProblemsAlgorithmica 2019: 2557–2591
     
  • Quasi-random Image Transi... - Download
    Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Quasi-random Image Transition and AnimationAustralian Journal of Intelligent Information Processing Systems 2019: 10–18
     
  • Selected open problems in... - Download
    Cechlárová, Katarína; Cseh, Ágnes; Manlove, David Selected open problems in Matching Under PreferencesBulletin of the European Association for Theoretical Computer Science 2019: 14–38
     
  • Detection and estimation ... - Download
    Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel Detection and estimation of additive outliers in seasonal time seriesComputational Statistics 2019: 1–17
     
  • On the transformation cap... - Download
    Michail, Othon; Skretas, George; Spirakis, G. Paul On the transformation capability of feasible mechanisms for programmable matterComputer and System Sciences 2019: 18–39
     
  • Nowhere-zero flow on some... - Download
    Reza Maimani, Hamid; Parsaei Majd, Leila Nowhere-zero flow on some products of signed graphsDiscrete Applied Mathematics 2019: 84–92
     
  • Surfing on the seascape: ... - Download
    Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian Surfing on the seascape: Adaptation in a changing environmentEvolution: International Journal of Organic Evolution 2019: 1356–1374
     
  • How to Draw a Planarizati... - Download
    Bläsius, Thomas; Rademacher, Marcel; Rutter, Ignaz How to Draw a PlanarizationGraph Algorithms and Applications 2019: 653–682
     
  • Paths to stable allocatio... - Download
    Cseh, Ágnes; Skutella, Martin Paths to stable allocationsInternational Journal of Game Theory 2019: 835–862
     
  • Multiple changepoint dete... - Download
    Cucina, Domenico; Rizzo, Manuel; Ursu, Eugen Multiple changepoint detection for periodic autoregressive models with an application to river flow analysisStochastic Environmental Research and Risk Assessment 2019: 1137–1157
     
  • Some Problems Concerning ... - Download
    Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic ProgressionThe Ramanujan Journal 2019: 545–565
     
  • Unbiasedness of Estimatio... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. Unbiasedness of Estimation-of-Distribution AlgorithmsTheoretical Computer Science 2019: 46–59
     
  • First-hitting times under... - Download
    Kötzing, Timo; Krejca, Martin S. First-hitting times under driftTheoretical Computer Science 2019: 51–69
     
  • The Stable Roommates Prob... - Download
    Cseh, Ágnes; Irving, Robert W.; Manlove, David F. The Stable Roommates Problem with Short ListsTheory of Computing Systems 2019: 128–149
     
  • Greedy Maximization of Fu... - Download
    Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2272–2279
     
  • Pareto Optimization for S... - Download
    Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Pareto Optimization for Subset Selection with Dynamic Cost ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2354–2361
     
  • From Hotelling to Load Ba... - Download
    Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander From Hotelling to Load Balancing: Approximation and the Principle of Minimum DifferentiationAutonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951
     
  • Efficiently Enumerating H... - Download
    Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingAlgorithm Engineering and Experiments (ALENEX) 2019: 130–143
     
  • Limit Learning Equivalenc... - Download
    Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca Limit Learning Equivalence StructuresAlgorithmic Learning Theory (ALT) 2019: 383–403
     
  • Extension of vertex cover... - Download
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of vertex cover and independent set in some classes of graphs and generalizationsInternational Conference on Algorithms and Complexity (CIAC) 2019: 124–136
     
  • Efficiently Generating Ge... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
    EATCS Best Paper Award
     
  • Extension of some edge gr... - Download
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of some edge graph problems: standard and parameterized complexityFundamentals of Computation Theory (FCT) 2019: 185–200
     
  • Multiplicative Up-Drift - Download
    Doerr, Benjamin; Kötzing, Timo Multiplicative Up-DriftGenetic and Evolutionary Computation Conference (GECCO) 2019
     
  • Deterministic Combinatori... - Download
    Alon, Noga; Chechik, Shiri; Cohen, Sarel Deterministic Combinatorial Replacement Paths and Distance Sensitivity OraclesInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1–12:14
     
  • The Satisfiability Thresh... - Download
    Friedrich, Tobias; Rothenberger, Ralf The Satisfiability Threshold for Non-Uniform Random 2-SATInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1–61:14
     
  • Graph and String Paramete... - Download
    Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality NumberInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16
     
  • Mixed Integer Programming... - Download
    Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment ProblemInternational Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554
     
  • Sharpness of the Satisfia... - Download
    Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151–6155
     
  • Random Subgroups of Ratio... - Download
    Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank Random Subgroups of RationalsMathematical Foundations of Computer Science (MFCS) 2019: 25:1–25:14
     
  • Near Optimal Algorithms F... - Download
    Chechik, Shiri; Cohen, Sarel Near Optimal Algorithms For The Single Source Replacement Paths ProblemSymposium on Discrete Algorithms (SODA) 2019: 2090–2109
     
  • Geometric Network Creatio... - Download
    Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation GamesSymposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332
     
  • From Graph Theory to Netw... - Download
    Friedrich, Tobias From Graph Theory to Network Science: The Natural Emergence of HyperbolicitySymposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
     
  • Pairwise Preferences in t... - Download
    Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemSymposium Theoretical Aspects of Computer Science (STACS) 2019: 21:1–21:16
     
  • On the Empirical Time Com... - Download
    Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M. On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase TransitionTools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134
     
  • Understanding the Effecti... - Download
    Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin Understanding the Effectiveness of Data Reduction in Public Transportation NetworksWorkshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101
     
  • Convergence and Hardness ... - Download
    Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David Convergence and Hardness of Strategic Schelling SegregationWeb and Internet Economics (WINE) 2019: 156–170
     
  • FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms ACM 2019
    Editorship
     
  • Theory of Randomized Optimization HeuristicsDagstuhl Reports 2019: 61–94
     
  • The Minimization of Rando... - Download
    Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Minimization of Random HypergraphsCoRR 2019
    ArXiv preprint
     

Journal Publications

2019

  • Hadwiger's conjecture for... - Download
    Issac, Davis; Chandran, L. Sunil; Zhou, Sanming Hadwiger’s conjecture for squares of 2-treesEuropean Journal of Combinatorics 2019: 159–174
     
  • Routing for On-Street Par... - Download
    Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin Routing for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124
     
  • Solving Problems with Unk... - Download
    Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Solving Problems with Unknown Solution Length at Almost No Extra CostAlgorithmica 2019: 703–748
     
  • Reoptimization Time Analy... - Download
    Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica 2019: 828–857
     
  • Island Models Meet Rumor ... - Download
    Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin Island Models Meet Rumor SpreadingAlgorithmica 2019: 886–915
     
  • New and Simple Algorithms... - Download
    Cseh, Ágnes; Matuschke, Jannik New and Simple Algorithms for Stable Flow ProblemsAlgorithmica 2019: 2557–2591
     
  • Quasi-random Image Transi... - Download
    Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Quasi-random Image Transition and AnimationAustralian Journal of Intelligent Information Processing Systems 2019: 10–18
     
  • Selected open problems in... - Download
    Cechlárová, Katarína; Cseh, Ágnes; Manlove, David Selected open problems in Matching Under PreferencesBulletin of the European Association for Theoretical Computer Science 2019: 14–38
     
  • Detection and estimation ... - Download
    Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel Detection and estimation of additive outliers in seasonal time seriesComputational Statistics 2019: 1–17
     
  • On the transformation cap... - Download
    Michail, Othon; Skretas, George; Spirakis, G. Paul On the transformation capability of feasible mechanisms for programmable matterComputer and System Sciences 2019: 18–39
     
  • Nowhere-zero flow on some... - Download
    Reza Maimani, Hamid; Parsaei Majd, Leila Nowhere-zero flow on some products of signed graphsDiscrete Applied Mathematics 2019: 84–92
     
  • Surfing on the seascape: ... - Download
    Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian Surfing on the seascape: Adaptation in a changing environmentEvolution: International Journal of Organic Evolution 2019: 1356–1374
     
  • How to Draw a Planarizati... - Download
    Bläsius, Thomas; Rademacher, Marcel; Rutter, Ignaz How to Draw a PlanarizationGraph Algorithms and Applications 2019: 653–682
     
  • Paths to stable allocatio... - Download
    Cseh, Ágnes; Skutella, Martin Paths to stable allocationsInternational Journal of Game Theory 2019: 835–862
     
  • Multiple changepoint dete... - Download
    Cucina, Domenico; Rizzo, Manuel; Ursu, Eugen Multiple changepoint detection for periodic autoregressive models with an application to river flow analysisStochastic Environmental Research and Risk Assessment 2019: 1137–1157
     
  • Some Problems Concerning ... - Download
    Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic ProgressionThe Ramanujan Journal 2019: 545–565
     
  • Unbiasedness of Estimatio... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. Unbiasedness of Estimation-of-Distribution AlgorithmsTheoretical Computer Science 2019: 46–59
     
  • First-hitting times under... - Download
    Kötzing, Timo; Krejca, Martin S. First-hitting times under driftTheoretical Computer Science 2019: 51–69
     
  • The Stable Roommates Prob... - Download
    Cseh, Ágnes; Irving, Robert W.; Manlove, David F. The Stable Roommates Problem with Short ListsTheory of Computing Systems 2019: 128–149
     
  • Greedy Maximization of Fu... - Download
    Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2272–2279
     
  • Pareto Optimization for S... - Download
    Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias Pareto Optimization for Subset Selection with Dynamic Cost ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2354–2361
     
  • From Hotelling to Load Ba... - Download
    Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander From Hotelling to Load Balancing: Approximation and the Principle of Minimum DifferentiationAutonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951
     
  • Efficiently Enumerating H... - Download
    Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingAlgorithm Engineering and Experiments (ALENEX) 2019: 130–143
     
  • Limit Learning Equivalenc... - Download
    Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca Limit Learning Equivalence StructuresAlgorithmic Learning Theory (ALT) 2019: 383–403
     
  • Extension of vertex cover... - Download
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of vertex cover and independent set in some classes of graphs and generalizationsInternational Conference on Algorithms and Complexity (CIAC) 2019: 124–136
     
  • Efficiently Generating Ge... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
    EATCS Best Paper Award
     
  • Extension of some edge gr... - Download
    Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension of some edge graph problems: standard and parameterized complexityFundamentals of Computation Theory (FCT) 2019: 185–200
     
  • Multiplicative Up-Drift - Download
    Doerr, Benjamin; Kötzing, Timo Multiplicative Up-DriftGenetic and Evolutionary Computation Conference (GECCO) 2019
     
  • Deterministic Combinatori... - Download
    Alon, Noga; Chechik, Shiri; Cohen, Sarel Deterministic Combinatorial Replacement Paths and Distance Sensitivity OraclesInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1–12:14
     
  • The Satisfiability Thresh... - Download
    Friedrich, Tobias; Rothenberger, Ralf The Satisfiability Threshold for Non-Uniform Random 2-SATInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1–61:14
     
  • Graph and String Paramete... - Download
    Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality NumberInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16
     
  • Mixed Integer Programming... - Download
    Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment ProblemInternational Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554
     
  • Sharpness of the Satisfia... - Download
    Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151–6155
     
  • Random Subgroups of Ratio... - Download
    Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank Random Subgroups of RationalsMathematical Foundations of Computer Science (MFCS) 2019: 25:1–25:14
     
  • Near Optimal Algorithms F... - Download
    Chechik, Shiri; Cohen, Sarel Near Optimal Algorithms For The Single Source Replacement Paths ProblemSymposium on Discrete Algorithms (SODA) 2019: 2090–2109
     
  • Geometric Network Creatio... - Download
    Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Geometric Network Creation GamesSymposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332
     
  • From Graph Theory to Netw... - Download
    Friedrich, Tobias From Graph Theory to Network Science: The Natural Emergence of HyperbolicitySymposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
     
  • Pairwise Preferences in t... - Download
    Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemSymposium Theoretical Aspects of Computer Science (STACS) 2019: 21:1–21:16
     
  • On the Empirical Time Com... - Download
    Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M. On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase TransitionTools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134
     
  • Understanding the Effecti... - Download
    Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin Understanding the Effectiveness of Data Reduction in Public Transportation NetworksWorkshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101
     
  • Convergence and Hardness ... - Download
    Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David Convergence and Hardness of Strategic Schelling SegregationWeb and Internet Economics (WINE) 2019: 156–170
     
  • FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms ACM 2019
    Editorship
     
  • Theory of Randomized Optimization HeuristicsDagstuhl Reports 2019: 61–94
     

Editorships

2019

  • FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms ACM 2019
    Editorship
     
  • Theory of Randomized Optimization HeuristicsDagstuhl Reports 2019: 61–94