April '24 | I started working on my DFG grant (project PACS) at HU Berlin in the group of Stefan Kratsch. |
December '23 | AAAI 2024 acceptance: Locally Rainbow Paths (with Leon Kellerhals and Malte Renken) |
July '23 | ECAI 2023 acceptance: Efficiently Computing Smallest Agreeable Sets (with Robert Bredereck and Nimrod Talmon) |
April '23 | IJCAI 2023 acceptance: Algorithmics of Egalitarian versus Equitable Sequences of Committees (with Eva Michelle Deltl and Robert Bredereck) |
October '22 | I started a postdoc position at TU Clausthal in the group of Robert Bredereck. |
May '22 | IJCAI'22 acceptances (2): When Votes Change and Committees Should (Not) (with Robert Bredereck and) Andrzej Kaczmarczyk), and Placing Green Bridges Optimally, with Habitats Inducing Cycles (with Maike Herkenrath, Francesco Grothe, and Leon Kellerhals). |
See also Google Scholar or DBLP
(Ordered by authors' last names).
Authors | Title | Journal | Conference | arxiv | anno |
---|---|---|---|---|---|
Cristina Bazgan, TF, André Nichterlein, Rolf Niedermeier, and Maximilian Stahlberg | A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths | Networks (2019) | arxiv | 2018 | |
Matthias Bentert, René van Bevern, TF, André Nichterlein, Rolf Niedermeier | Polynomial-time data reduction for weighted problems beyond additive goal functions | Discrete Applied Mathematics | arXiv ✎ | 2019 | |
Matthias Bentert, TF, André Nichterlein, and |
Parameterized Aspects of Triangle Enumeration
abstractListing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter). |
JCSS(SI) (2019) | FCT 2017 | arXiv ✎ | 2017 |
René van Bevern, TF, George B. Mertzios, |
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs | Discrete Optimization (2018) | IPEC 2016 | arXiv | 2016 |
René van Bevern, TF, Oxana Yu. Tsidulko | Parameterized algorithms and data reduction for the short secluded s-t-path problem
abstractGiven a graph G=(V,E), two vertices s,t in V, and two integers k,l, the Short Secluded Path problem is to find a simple s-t-path with at most k vertices and l neighbors. We study the parameterized complexity of the problem with respect to four structural graph parameters: the vertex cover number, treewidth, feedback vertex number, and feedback edge number. In particular, we completely settle the question of the existence of problem kernels with size polynomial in these parameters and their combinations with k and l. We also obtain a 2^O(w) l^2 n-time algorithm for graphs of treewidth w, which yields subexponential-time algorithms in several graph classes. |
Networks (2020) | ATMOS 2018 ✎ | arxiv | 2018 |
René van Bevern, TF, Oxana Yu. Tsidulko | On approximate data reduction for the Rural Postman Problem: Theory and experiments
abstractGiven an undirected graph with edge weights and a subset R of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. We prove that RPP is WK[1]‐complete parameterized by the number and weight d of edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial‐time compressed to instances of size polynomial in d unless the polynomial‐time hierarchy collapses. In contrast, denoting by b ≤ 2d the number of vertices incident to an odd number of edges of R and by c ≤ d the number of connected components formed by the edges in R, we show how to reduce any RPP instance I to an RPP instance I′ with 2b + O(c/ϵ) vertices in O(n3) time so that any α‐approximate solution for I′ gives an α(1 + ϵ)‐approximate solution for I, for any α ≥ 1 and ϵ > 0. That is, we provide a polynomial‐size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide‐spread benchmark data sets as well as on two real snow plowing instances from Berlin. We also make first steps toward a PSAKS for the parameter c. |
Networks (2020) | MOTOR 2019 | arXiv | 2018 |
Robert Bredereck, TF, Andrzej Kaczmarczyk | When Votes Change and Committees Should (Not)
abstractElecting a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-dependent multistage models based on simple Plurality voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be "easier" than being conservative: If the (upper- resp. lower-) bound on the size of symmetric differences is constant, the conservative model remains NP-hard while the revolutionary model becomes polynomial-time solvable. |
IJCAI 2022 | arXiv | 2020 | |
Robert Bredereck, TF, Nimrod Talmon | Efficiently Computing Smallest Agreeable Sets
abstractWe study the computational complexity of identifying a small agreeable subset of items. A subset of items is agreeable if every agent does not prefer its complement set. We study settings in which agents either can assign arbitrary utilities to the items; can approve or disapprove the items; or can rank the items (in which case we consider Borda utilities). We prove that deciding whether an agreeable set exists is NP-hard for all variants; and we perform a parameterized analysis regarding the following natural parameters: the number of agents, the number of items, and the upper bound on the size of the agreeable set in question. |
ECAI 2023 | 2023 | ||
Markus Brill, TF, Vincent Froese, Brijnesh Jain, Rolf Niedermeier, and David Schultz | Exact Mean Computation in Dynamic Time Warping Spaces
abstractDynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minimizing the Fr\'echet function) is a challenging computational problem, so far solved by several heuristic, inexact strategies. We spot several inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Our contributions comprise an exact dynamic program computing a mean (useful for benchmarking and evaluating known heuristics). Empirical evaluations reveal significant deficits of the state-of-the-art heuristics in terms of their output quality. Finally, we give an exact polynomial-time algorithm for the special case of binary time series. |
Data Min. Knowl. Discov. (2019) | SDM 2018 ✎ | arXiv | 2017 |
Dario Cavallaro, TF | 3-Coloring on Regular, Planar, and Ordered Hhttpsamiltonian Graphs
abstractWe prove that 3-Coloring remains NP-hard on 4- and 5-regular planar Hamiltonian graphs, strengthening the results of Dailey [Disc. Math.'80] and Fleischner and Sabidussi [J. Graph. Theor.'02]. Moreover, we prove that 3-Coloring remains NP-hard on p-regular Hamiltonian graphs for every p≥6 and p-ordered regular Hamiltonian graphs for every p≥3. |
arXiv | 2021 | ||
Dario Cavallaro, TF | Feedback Vertex Set on Hamiltonian Graphs
abstractWe study the computational complexity of Feedback Vertex Set on subclasses of Hamiltonian graphs. In particular, we consider Hamiltonian graphs that are regular or are planar and regular. Moreover, we study the less known class of p-Hamiltonian-ordered graphs, which are graphs that admit for any p-tuple of vertices a Hamiltonian cycle visiting them in the order given by the tuple. We prove that Feedback Vertex Set remains NP-hard in these restricted cases, even if a Hamiltonian cycle is additionally given as part of the input. |
WG'21 | arXiv | 2021 | |
Henning Fernau, TF, Danny Hermelin, |
Diminishable Parameterized Problems and Strict Polynomial Kernelization
abstractKernelization – a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems – plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP⊈coNP/poly. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Müller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of P≠NP, an assumption being weaker than the assumption of NP⊈coNP/poly. Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter. |
Computability (2020) | CiE 2018 ✎ | arXiv | 2016 |
Eva Michelle Deltl, TF, Robert Bredereck | Algorithmics of Egalitarian versus Equitable Sequences of Committees
abstractWe study the election of sequences of committees, where in each of tau levels (e.g. modeling points in time) a committee consisting of k candidates from a common set of m candidates is selected. For each level, each of n agents (voters) may nominate one candidate whose selection would satisfy her. We are interested in committees which are good with respect to the satisfaction per day and per agent. More precisely, we look for egalitarian or equitable committee sequences. While both guarantee that at least x agents per day are satisfied, egalitarian committee sequences ensure that each agent is satisfied in at least y levels while equitable committee sequences ensure that each agent is satisfied in exactly y levels. We analyze the parameterized complexity of finding such committees for the parameters n, m, k, tau, x, and y, as well as combinations thereof. |
IJCAI 2023 | arxiv | 2023 | |
TF | A Multistage View on 2-Satisfiability
abstractWe study q-SAT in the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence of q-CNF fomulas and a non-negative integer d, the question is whether there is a sequence of satisfying truth assignments such that for every two consecutive truth assignments, the number of variables whose values changed is at most d. We prove that Multistage 2-SAT is NP-hard even in quite restricted cases. Moreover, we present parameterized algorithms (including kernelization) for Multistage 2-SAT and prove them to be asymptotically optimal. |
CIAC 2021 | arxiv | 2020 | |
TF, Meike Hatzel, Steffen Härtlein, Hendrik Molter, and Henning Seidler | The Minimum Shared Edges Problem on Grid-like Graphs
abstractWe study the 𝖭𝖯-hard Minimum Shared Edges (MSE) problem on graphs: decide whether it is possible to route p paths from a start vertex to a target vertex in a given graph while using at most k edges more than once. We show that MSE can be decided on bounded (i.e. finite) grids in linear time when both dimensions are either small or large compared to the number p of paths. On the contrary, we show that MSE remains 𝖭𝖯-hard on subgraphs of bounded grids. Finally, we study MSE from a parametrised complexity point of view. It is known that MSE is fixed-parameter tractable with respect to the number p of paths. We show that, under standard complexity-theoretical assumptions, the problem parametrised by the combined parameter k, p, maximum degree, diameter, and treewidth does not admit a polynomial-size problem kernel, even when restricted to planar graphs. |
WG 2017 | arXiv | 2017 | |
TF, Danny Hermelin, André Nichterlein, and |
Fractals for Kernelization Lower Bounds | SIAM J. Discrete Math. (2018) ✎ | ICALP 2016 ✎ | arxiv ✎ | 2015 |
TF, Leon Kellerhals | Placing Green Bridges Optimally, with a Multivariate Analysis
abstractWe study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop different problem models for this task and study them from a computational complexity and parameterized algorithmics perspective. |
CiE 2021 | arxiv | 2021 | |
TF, Leon Kellerhals, Malte Renken | Locally Rainbow Paths
abstractWe introduce the algorithmic problem of finding a locally rainbow path of length l connecting two distinguished vertices s and t in a vertex-colored directed graph. Herein, a path is locally rainbow if between any two visits of equally colored vertices, the path traverses consecutively at least r differently colored vertices. This problem generalizes the well-known problem of finding a rainbow path. It finds natural applications whenever there are different types of resources that must be protected from overuse, such as crop sequence optimization or production process scheduling. We show that the problem is computationally intractable even if r=2 or if one looks for a locally rainbow among the shortest paths. On the positive side, if one looks for a path that takes only a short detour (i.e., it is slightly longer than the shortest path) and if r is small, the problem can be solved efficiently. Indeed, the running time of the respective algorithm is near-optimal unless the ETH fails. |
AAAI 2024 | arxiv | 2023 | |
TF, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and |
When can Graph Hyperbolicity be computed in Linear Time? | Algorithmica (2019) | WADS 2017 | arXiv | 2017 |
TF, Stefan Kratsch, Rolf Niedermeier, and |
The Parameterized Complexity of the Minimum Shared Edges Problem | JCSS (2019) | FSTTCS 2015 | arxiv | 2016 |
TF, Steffen Kriewald, Anselmo García Cantú Ros, Bin Zhou, Dominik E. Reusser, Jürgen P. Kropp, and Diego Rybski | The Size Distribution, Scaling Properties and Spatial Organization of Urban Clusters: A Global and Regional Perspective | IJGI, ISPRS Int. J. Geo-Inf. (2016) | arxiv | 2014 | |
TF, Pascal Kunz | Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring | SAND 2022 | arxiv | 2014 | |
TF, George B. Mertzios, and André Nichterlein | Kernelization Lower Bounds for Finding Constant Size Subgraphs
abstractKernelization is an important tool in parameterized algorithmics. The goal is to reduce the input instance of a parameterized problem in polynomial time to an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture. |
CiE 2018 ✎ | arXiv | 2017 | |
TF, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche | Temporal Graph Classes: A View Through Temporal Separators
abstractWe investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s, z)-Separation problem is NP-hard, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph---there we observe polynomial-time solvability in the case of bounded treewidth---as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. |
Theor. Comput. Sci. (2020) | WG 2018 ✎ | arXiv | 2018 |
TF, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche | As Time Goes By: Reflections on Treewidth for Temporal Graphs
abstractTreewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh algorithmic views on temporal tree decompositions and temporal treewidth. We review and explain some of the recent work together with some encountered pitfalls, and we point out challenges for future research. |
Treewidth, Kernels, and Algorithms 2020 ✎ | arXiv | 2018 | |
TF, Marco Morik, and Manuel Sorge | The Complexity of Routing with Few Collisions
abstractWe study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph G with two distinct terminal vertices and two positive integers p and k, the question is whether one can connect the terminals by at least p routes (e.g. paths) such that at most k edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if k is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary k and on directed graphs if k is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs. |
JCSS(SI) (2019) | FCT 2017 | arXiv ✎ | 2017 |
TF, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche | Multistage Vertex Cover
abstractCovering all edges of a graph by a minimum number of vertices, this is the NP-hard Vertex Cover problem, is among the most fundamental algorithmic tasks. Following a recent trend in studying dynamic and temporal graphs, we initiate the study of Multistage Vertex Cover. Herein, having a series of graphs with same vertex set but over time changing edge sets (known as temporal graph consisting of various layers), the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that the two vertex cover sets between two sub- sequent layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of the most natural parameterizations. |
Theory of Computing Systems (2022) | IPEC 2019 | arxiv | 2019 |
TF, Rolf Niedermeier, Carsten Schubert, Philipp Zschoche | Multistage s-t Path: Confronting Similarity with Dissimilarity
abstractAddressing a quest by Gupta et al. [ICALP'14], we provide a first, comprehensive study of finding a short s-t path in the multistage graph model, referred to as the Multistage s-t Path problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short s-t paths in each graph ("snapshot") such that in the resulting path sequence the consecutive s-t paths are "similar". We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that the two variants of Multistage s-t Path are already NP-hard for an input sequence of only two graphs. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, we prove parameterized hardness (W[1]-hardness) regarding the size of the path sequence (solution size) for both variants, vertex- and edge-similarity. As a novel conceptual contribution, we then modify the multistage model by asking for dissimilar consecutive paths. As one of the main results, we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, thereby contrasting our W[1]-hardness proof of the corresponding similarity case. |
Algorithmica | ISAAC 2020 | arxiv | 2020 |
TF, Piotr Skowron, Mervin Triphaus, Kai Wilker | Fair Knapsack
abstractWe study the following multiagent variant of the knapsack problem. We are given a set of items, a set of voters, and a value of the budget; each item is endowed with a cost and each voter assigns to each item a certain value. The goal is to select a subset of items with the total cost not exceeding the budget, in a way that is consistent with the voters' preferences. Since the preferences of the voters over the items can vary significantly, we need a way of aggregating these preferences, in order to select the socially most preferred valid knapsack. We study three approaches to aggregating voters preferences, which are motivated by the literature on multiwinner elections and fair allocation. This way we introduce the concepts of individually best, diverse, and fair knapsack. We study computational complexity (including parameterized complexity, and complexity under restricted domains) of computing the aforementioned concepts of multiagent knapsacks. |
AAAI 2019 | arXiv | 2017 | |
TF, Manuel Sorge | The Minimum Shared Edges Problem on Planar Graphs | arXiv | 2016 | ||
Ramana Venkata Gudipudi, TF, Anselmo García Cantú Ros, Carsten Walther, and Jürgen P. Kropp | City Density and CO2 Efficiency
abstractCities play a vital role in the global climate change mitigation agenda. City population density is one of the key factors that influence urban energy consumption and the subsequent GHG emissions. However, previous research on the relationship between population density and GHG emissions led to contradictory results due to urban/rural definition conundrum and the varying methodologies for estimating GHG emissions. This work addresses these ambiguities by employing the City Clustering Algorithm (CCA) and utilizing the gridded CO2 emissions data. Our results, derived from the analysis of all inhabited areas in the US, show a sub-linear relationship between population density and the total emissions (i.e. the sum of on-road and building emissions) on a per capita basis. Accordingly, we find that doubling the population density would entail a reduction in the total CO2 emissions in buildings and on-road sectors typically by at least 42%. Moreover, we find that population density exerts a higher influence on on-road emissions than buildings emissions. From an energy consumption point of view, our results suggest that on-going urban sprawl will lead to an increase in on-road energy consumption in cities and therefore stresses the importance of developing adequate local policy measures to limit urban sprawl. |
Energy Policy (2016) | 2016 | ||
Maike Herkenrath, TF, Francesco Grothe, Leon Kellerhals | Placing Green Bridges Optimally, with Habitats Inducing Cycles
abstractChoosing the placement of wildlife crossings (i.e., green bridges) to reconnect animal species' fragmented habitats is among the 17 goals towards sustainable development by the UN. We consider the following established model: Given a graph whose vertices represent the fragmented habitat areas and whose weighted edges represent possible green bridge locations, as well as the habitable vertex set for each species, find the cheapest set of edges such that each species' habitat is connected. We study this problem from a theoretical (algorithms and complexity) and an experimental perspective, while focusing on the case where habitats induce cycles. We prove that the NP-hardness persists in this case even if the graph structure is restricted. If the habitats additionally induce faces in plane graphs however, the problem becomes efficiently solvable. In our empirical evaluation we compare this algorithm as well as ILP formulations for more general variants and an approximation algorithm with another. Our evaluation underlines that each specialization is beneficial in terms of running time, whereas the approximation provides highly competitive solutions in practice. |
IJCAI 2022 | arxiv | 2021 | |
Max-Jonathan Luckow, TF | On the computational complexity of length- and neighborhood-constrained path problems
abstractFinding paths in graphs is a fundamental graph-theoretic task. In this work, we are concerned with finding a path with some constraints on its length and the number of vertices neighboring the path, that is, being outside of and incident with the path. Herein, we consider short and long paths on the one side, and small and large neighborhoods on the other side—yielding four decision problems. We show that all four problems are NP-complete, even in planar graphs with small maximum degree. Moreover, we study all four variants when parameterized by a bound k on the length of the path, by a bound ℓ on the size of neighborhood, and by k+ℓ. |
IPL (2020) | arxiv | 2018 | |
Anselmo García Cantú Ros, TF, and Jürgen P. Kropp | Variance-based control of regime shifts: bistability and oscillations | under review | arXiv | 2014 | |
Philipp Zschoche, TF, Hendrik Molter, and Rolf Niedermeier | The Complexity of Finding Small Separators in Temporal Graphs
abstractTemporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that contain arbitrarily many edges per time step (non- strict) and paths that contain at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial- time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores. |
JCSS (2020) | MFCS 2018 ✎ | arXiv | 2017 |
Doctoral Thesis.
TF. Elements of Efficient Data Reduction: Fractals, Diminishers, Weights and Neighborhoods. Technische Universität Berlin.
Master Thesis.
TF. The Parameterized Complexity of Finding Paths with Shared Edges. Technische Universität Berlin.
Bachelor Thesis.
TF. Kritisches Verhalten eines verdünnten zufälligen Polymers. Technische Universität Berlin.
2019.
ALGO, September, 2019.
ARDA, August, 2019.
2018.
18th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS '18). In Helsinki, Finland, August 23 – 24 , 2018.
Dagstuhl Seminar 18281: Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices. In Dagstuhl, Germany, July 8 – 13 , 2018.
44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'18). In Lübbenau, Germany, June 27-29, 2018.
2017.
43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17). In Eindhoven, The Netherlands, June 21-23, 2017.
2015.
Workshop on Kernelization (WORKER) 2015. In Nordfjordeid, Norway. June 2015.
2021.
The 12th International Conference on Algorithms and Complexity (CIAC 2021). Online.
2020.
Algorithmic Aspects of Temporal Graphs (AAGT) III (ICALP 2020 satellite workshop), July, 2020.
2019.
KolKom 2019, September, 2019.
33rd AAAI Conference on Artificial Intelligence (AAAI '18) . Honolulu, Hawaii, USA, Jan 27-Feb 01
2018.
Conference on Computability in Europe (CiE'18) . Kiel, Germany, July 30-August 3
SIAM International Conference on Data Mining 2018 (SDM'18) . San Diego, CA, USA, May 3-5
75. Workshop über Algorithmen und Komplexität . Universität Ulm, Ulm, Germany, April 10-11
2017.
74. Workshop über Algorithmen und Komplexität . Universität zu Lübeck, Lübeck, Germany, November 23-24
15th Algorithms and Data Structures Symposium (WADS) . St. John's, Newfundland, Canada, July 31-August 2
2016.
72. Workshop über Algorithmen und Komplexität . Leibniz Universität Hannover, Institut für Theoretische Informatik.
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) . In Aarhus, Denmark, August 24-26.
43rd International Colloquium on Automata, Languages and Programming (ICALP 2016). In Rome, Italy. July 2016.
2015.
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). In Bangalore, India. December 2015.
7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW). In Aussois, France. October 2015. Slides.
The size distribution, scaling properties and spatial organization of urban clusters: a global and regional perspective. Verhandlungen der Deutschen Physikalischen Gesellschaft, AKE 14: Physics of Sustainability and Human-Nature Interactions I, at Technische Universität Berlin, Germany. March 2015.
2023.
Karla Braun Scoring-Allokationsfunktionen als Approximation für faire Ressourcenverteilung. TU Clausthal, October 2023, Bachelor thesis.
Amela Pucic. Algorithmik der simultanen Evakuierung auf temporal abnehmenden Graphen. Technische Universität Berlin, June 2023, Bachelor thesis.
Christian Wallisch. Placing Green Bridges to Reconnect Habitats Densely: Algorithms and Complexity. Technische Universität Berlin, April 2023, Bachelor thesis.
Christopher Denker. The Parameterized Complexity of Multistage Problem Variants: Size versus Similarity. Technische Universität Berlin, January 2023, Master thesis.
2022.
Duc Thai Vu. Investigating the Structure of Random Temporal Graphs: Theory and Experiments. Technische Universität Berlin, August 2022, Bachelor thesis.
Louisa Nau. Algorithmic Complexity of Successive Evacuation in Decaying Temporal Graphs. Technische Universität Berlin, January 2022, Bachelor thesis.
2021.
Valentin Rohm. From Temporal Graphs to Temporal Trees: Concepts, Algorithms, and Properties. Technische Universität Berlin, November 2021, Master thesis.
Maike Herkenrath. The Influence of Habitat Structure on the Algorithmic Complexity of Placing Green Bridges. Technische Universität Berlin, November 2021, Bachelor thesis.
Burak Arinalp. Multistage Committee Elections: Beyond Plurality Voting. Technische Universität Berlin, March 2021, Bachelor thesis.
2020.
Laurenz Julian Rasche. Synergie zwischen ÖPNV und Radfahren, modelliert als Routing in Temporalen Graphen.. Technische Universität Berlin, December, 2020. Bachelor thesis.
Pacal Kunz. Proximity and Intractibility - Revisiting Classic Graph Problems.. Technische Universität Berlin, December, 2020. Master thesis.
2019.
Carsten Schubert. Preserving Paths in Temporal Graphs. Technische Universität Berlin, September, 2019. Bachelor thesis.
Dario Cavallaro. Hamiltonicity and the computational complexity of graph problems. Technische Universität Berlin, Juli, 2019. Bachelor thesis.
2018.
Leon Kellerhals. Parameterized Algorithms for Network Flows. Technische Universität Berlin, June 2018, Master thesis.
Valentin Rohm. Vertex Cover Under Time Constraints. Technische Universität Berlin, November 2018, Bachelor thesis.
2017.
Philipp Zschoche. On Finding Separators in Temporal Graphs. Technische Universität Berlin, August 2017, Master thesis.
Max-Jonathan Luckow. Paths under Neighborhood Constraints — Algorithms and Complexity. Technische Universität Berlin, April 2017, Bachelor thesis.
2016.
Matthias Bentert. Parametrised Algorithms for Finding Triangles in Graphs - Detection, Counting and Enumeration. Technische Universität Berlin, December 2016, Master thesis.
Marco Morik. The Complexity of Routing with Collision Avoidance. Technische Universität Berlin, June, 2016. Bachelor thesis.
Maximilian Stahlberg. Finding the Most Vital Edges for Shortest Paths - Algorithms and Complexity for Special Graph Classes. Technische Universität Berlin, February, 2016. Bachelor thesis.
Analysis (and more) Scripts by Dirk Ferus (only in German).
Scripts by Wolfgang König (in the context of probabilistic theory, only in German): in particular, Wahrscheinlichkeitstheorie I+II and Stochastische Algorithmen.
Script by Stefan Felsner (together with students) about Graph theory (only in German)
Martin Aigner and Günter M. Ziegler: Proof from THE BOOK
Orthodromic Spatial Clustering