Outputs (261)

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (2016)
Presentation / Conference Contribution

For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with do... Read More about Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

A linear kernel for finding square roots of almost planar graphs (2016)
Presentation / Conference Contribution

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. W... Read More about A linear kernel for finding square roots of almost planar graphs.

Stably computing order statistics with arithmetic population protocols (2016)
Presentation / Conference Contribution

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Popula... Read More about Stably computing order statistics with arithmetic population protocols.

Colouring diamond-free graphs (2016)
Presentation / Conference Contribution

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof i... Read More about Colouring diamond-free graphs.

The Complexity of General-Valued CSPs (2015)
Presentation / Conference Contribution

An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values spec... Read More about The Complexity of General-Valued CSPs.

Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time (2012)
Presentation / Conference Contribution

Graph editing to a given degree sequence (2016)
Presentation / Conference Contribution

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σσ by at most k vertex or edge deletions and edge addition... Read More about Graph editing to a given degree sequence.

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins (2016)
Presentation / Conference Contribution

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be... Read More about Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins.

Constraint Satisfaction Problems over the Integers with Successor (2015)
Presentation / Conference Contribution

A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z;succ)(Z;succ), i.e., over the integers with the successor function. Our main... Read More about Constraint Satisfaction Problems over the Integers with Successor.

Reducing the clique and chromatic number via edge contractions and vertex deletions (2016)
Presentation / Conference Contribution

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the c... Read More about Reducing the clique and chromatic number via edge contractions and vertex deletions.

Finding secluded places of special interest in graphs (2017)
Presentation / Conference Contribution

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired verte... Read More about Finding secluded places of special interest in graphs.

Threshold Load Balancing with Weighted Tasks (2015)
Presentation / Conference Contribution

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m > n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a thr... Read More about Threshold Load Balancing with Weighted Tasks.

Randomized Renaming in Shared Memory Systems (2015)
Presentation / Conference Contribution

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were develo... Read More about Randomized Renaming in Shared Memory Systems.

On temporally connected graphs of small cost (2016)
Presentation / Conference Contribution

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u t... Read More about On temporally connected graphs of small cost.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results... Read More about Open problems on graph coloring for special graph classes.

Bounding the clique-width of H-free split graphs (2015)
Presentation / Conference Contribution

A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main res... Read More about Bounding the clique-width of H-free split graphs.

Bounding the Clique-Width of H-free Chordal Graphs (2015)
Presentation / Conference Contribution

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs (2016)
Presentation / Conference Contribution

We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restr... Read More about Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.

Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs (2015)
Presentation / Conference Contribution

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a funda... Read More about Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)G=(N,E), with an integer vertex capacity function b and an edge weighting w. The set N consists of a number of players that... Read More about The stable fixtures problem with payments.