Outputs (261)

Colouring graphs of bounded diameter in the absence of small cycles (2021)
Presentation / Conference Contribution

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two non-adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss (2021)
Presentation / Conference Contribution

In this paper we introduce two methods of improving real-time object grasping performance from monocular colour images in an end-to-end CNN architecture. The first is the addition of an auxiliary task during model training (multi-task learning). Our... Read More about Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss.

Exact and approximate algorithms for computing a second Hamiltonian cycle (2020)
Presentation / Conference Contribution

A classic result by Stockmeyer [Stockmeyer, 1974] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic... Read More about Exact and approximate algorithms for computing a second Hamiltonian cycle.

Clique-Width: Harnessing the Power of Atoms (2020)
Presentation / Conference Contribution

Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of... Read More about Clique-Width: Harnessing the Power of Atoms.

Sherali-Adams and the binary encoding of combinatorial principles (2020)
Presentation / Conference Contribution

We consider the Sherali-Adams ( SA ) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Principle and the Least Number Principle, it is known that linear rank is r... Read More about Sherali-Adams and the binary encoding of combinatorial principles.

Interference-free walks in time: temporally disjoint paths (2021)
Presentation / Conference Contribution

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: temporally disjoint paths.

Contracting to a longest path in H-free graphs (2020)
Presentation / Conference Contribution

The Path Contraction problem has as input a graph G and an integer k and is to decide if G can be modified to the k-vertex path P_k by a sequence of edge contractions. A graph G is H-free for some graph H if G does not contain H as an induced subgrap... Read More about Contracting to a longest path in H-free graphs.

Computing subset transversals in H-free graphs (2020)
Presentation / Conference Contribution

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph... Read More about Computing subset transversals in H-free graphs.

QCSP monsters and the demise of the chen conjecture (2020)
Presentation / Conference Contribution

We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ is a finite language over 3 elements which contains all constants. In particular, su... Read More about QCSP monsters and the demise of the chen conjecture.

Autoencoders Without Reconstruction for Textural Anomaly Detection (2021)
Presentation / Conference Contribution

Automatic anomaly detection in natural textures is a key component within quality control for a range of high-speed, high-yield manufacturing industries that rely on camera-based visual inspection techniques. Targeting anomaly detection through the u... Read More about Autoencoders Without Reconstruction for Textural Anomaly Detection.

Steiner trees for hereditary graph classes (2020)
Presentation / Conference Contribution

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (... Read More about Steiner trees for hereditary graph classes.

Computing maximum matchings in temporal graphs (2020)
Presentation / Conference Contribution

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps... Read More about Computing maximum matchings in temporal graphs.

Independent transversals versus transversals (2019)
Presentation / Conference Contribution

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two... Read More about Independent transversals versus transversals.

Resolution and the binary encoding of combinatorial principles (2019)
Presentation / Conference Contribution

Res(s) is an extension of Resolution working on s-DNFs. We prove tight n (k) lower bounds for the size of refutations of the binary version of the k-Clique Principle in Res(o(log log n)). Our result improves that of Lauria, Pudlák et al. [27] who pro... Read More about Resolution and the binary encoding of combinatorial principles.

Generalized matching games for international kidney exchange (2019)
Presentation / Conference Contribution

Deleting edges to restrict the size of an epidemic in temporal networks (2019)
Presentation / Conference Contribution

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of good... Read More about Deleting edges to restrict the size of an epidemic in temporal networks.

Tight & Simple Load Balancing (2019)
Presentation / Conference Contribution

We consider the following load balancing process for m tokens distributed arbitrarily among n nodes connected by a complete graph. In each time step a pair of nodes is selected uniformly at random. Let ℓ 1 and ℓ 2 be their respective number of tokens... Read More about Tight & Simple Load Balancing.

Acyclic, star and injective colouring: a complexity picture for H-free graphs (2020)
Presentation / Conference Contribution

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, sta... Read More about Acyclic, star and injective colouring: a complexity picture for H-free graphs.

On cycle transversals and their connected variants in the absence of a small linear forest (2019)
Presentation / Conference Contribution

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and Odd Cycle Transversal by showing that they can be solved in polynomial time... Read More about On cycle transversals and their connected variants in the absence of a small linear forest.

Tree pivot-minors and linear rank-width (2019)
Presentation / Conference Contribution

Treewidth and its linear variant path-width play a central role for the graph minor relation. Rank-width and linear rank-width do the same for the graph pivot-minor relation. Robertson and Seymour (1983) proved that for every tree T there exists a co... Read More about Tree pivot-minors and linear rank-width.