Outputs (30)
Classifying Subset Feedback Vertex Set for H-free graphs (2022)
Presentation / Conference Contribution
In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also... Read More about Classifying Subset Feedback Vertex Set for H-free graphs.
Few induced disjoint paths for H-free graphs (2022)
Presentation / Conference Contribution
Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs... Read More about Few induced disjoint paths for H-free graphs.
An algorithmic framework for locally constrained homomorphisms (2022)
Presentation / Conference Contribution
A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decision... Read More about An algorithmic framework for locally constrained homomorphisms.
The complexity of growing a graph (2022)
Presentation / Conference Contribution
We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph in... Read More about The complexity of growing a graph.
Payment scheduling in the Interval Debt Model (2023)
Presentation / Conference Contribution
The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.
Evaluating Gaussian Grasp Maps for Generative Grasping Models (2022)
Presentation / Conference Contribution
Generalising robotic grasping to previously unseen objects is a key task in general robotic manipulation. The current method for training many antipodal generative grasping models rely on a binary ground truth grasp map generated from the centre thir... Read More about Evaluating Gaussian Grasp Maps for Generative Grasping Models.
The complexity of computing optimum labelings for temporal connectivity (2022)
Presentation / Conference Contribution
A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally c... Read More about The complexity of computing optimum labelings for temporal connectivity.
The Complexity of L(p,q)-Edge-Labelling (2022)
Presentation / Conference Contribution
The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.
Computing Balanced Solutions for Large International Kidney Exchange Schemes (2022)
Presentation / Conference Contribution
To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countr... Read More about Computing Balanced Solutions for Large International Kidney Exchange Schemes.
The complexity of temporal vertex cover in small-degree graphs (2022)
Presentation / Conference Contribution
Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆- TVC for time-windows of a fixed-length ∆) have been established... Read More about The complexity of temporal vertex cover in small-degree graphs.
Partitioning H-free graphs of bounded diameter (2021)
Presentation / Conference Contribution
A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.
QCSP on reflexive tournaments (2021)
Presentation / Conference Contribution
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.
Infinite Balanced Allocation via Finite Capacities (2021)
Presentation / Conference Contribution
We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are n bins (servers) with a limited capacity (buffer) of size c=c(n)∈N . Given a fixed arrival rate λ=λ(n)∈(0,1) , in every round λn new ball... Read More about Infinite Balanced Allocation via Finite Capacities.
Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs (2021)
Presentation / Conference Contribution
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvabl... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs.
Bounding the mim-width of hereditary graph classes (2020)
Presentation / Conference Contribution
A large number of NP-hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In thi... Read More about Bounding the mim-width of hereditary graph classes.
The complexity of transitively orienting temporal graphs (2021)
Presentation / Conference Contribution
In a temporal network with discrete time-labels on its edges, entities and information can only “flow” along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless,... Read More about The complexity of transitively orienting temporal graphs.
Equitable scheduling on a single machine (2021)
Presentation / Conference Contribution
We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem... Read More about Equitable scheduling on a single machine.
Computing weighted subset transversals in H-free graphs (2021)
Presentation / Conference Contribution
For the Odd Cycle Transversal problem, the task is to nd a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal requires S to intersect only those odd cycles that include a vertex of a disting... Read More about Computing weighted subset transversals in H-free graphs.
Injective colouring for H-free graphs (2021)
Presentation / Conference Contribution
A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also... Read More about Injective colouring for H-free graphs.