![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Article
Open AccessThe Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk ...
-
Article
The Minimum Feasible Tileset Problem
We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario ca...
-
Chapter and Conference Paper
Your Rugby Mates Don’t Need to Know Your Colleagues: Triadic Closure with Edge Colors
Given an undirected graph \(G=(V,E)\) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edg...
-
Chapter and Conference Paper
Efficient Algorithms for Measuring the Funnel-Likeness of DAGs
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees for directed graphs that is mo...
-
Chapter and Conference Paper
The Parameterized Complexity of Centrality Improvement in Networks
The centrality of a vertex v in a network intuitively captures how important v is for communication in the network. The task of improving the centrality of a vertex has many applications, as a higher centrality o...
-
Article
On Kernelization and Approximation for the Vector Connectivity Problem
In the Vector Connectivity problem we are given an undirected graph \(G=(V,E)\) ...
-
Chapter and Conference Paper
The Complexity of Routing with Few Collisions
We 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 an...
-
Chapter and Conference Paper
Assessing the Computational Complexity of Multi-layer Subgraph Detection
Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple types of relationships (edges in ...
-
Chapter and Conference Paper
Twins in Subdivision Drawings of Hypergraphs
Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Din...
-
Chapter and Conference Paper
Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments
We consider the following problem. Given a graph and a rational number \(\mu \) ,
-
Chapter and Conference Paper
The Minimum Feasible Tileset Problem
We consider the Minimum Feasible Tileset problem: Given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed...
-
Chapter and Conference Paper
Finding Highly Connected Subgraphs
A popular way of formalizing clusters in networks are highly connected subgraphs, that is, subgraphs of k vertices that have edge connectivity larger than k/2 (equivalently, minimum degree larger than k/2). We ex...
-
Chapter and Conference Paper
A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems
We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from...
-
Chapter and Conference Paper
Effective and Efficient Data Reduction for the Subset Interconnection Design Problem
The NP-hard Subset Interconnection Design problem is motivated by applications in designing vacuum systems and scalable overlay networks. It has as input a set V and a collection of subsets V 1, V
-
Chapter and Conference Paper
On the Parameterized Complexity of Computing Graph Bisections
The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been tho...
-
Chapter and Conference Paper
Finding Dense Subgraphs of Sparse Graphs
We investigate the computational complexity of the Densest- k -Subgraph (D k S) problem, where the input is an undirected graph G = (V,E) and one wants to f...
-
Chapter and Conference Paper
Exploiting a Hypergraph Model for Finding Golomb Rulers
Golomb rulers are special rulers where for any two marks it holds that the distance between them is unique. They find applications in positioning of radio channels, radio astronomy, communication networks, and...
-
Chapter and Conference Paper
From Few Components to an Eulerian Graph by Adding Arcs
Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs of minimum total cost. EE is NP-hard and has been shown fixed-parameter tractable with res...
-
Chapter and Conference Paper
A New View on Rural Postman Based on Eulerian Extension and Matching
We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized ...
-
Chapter and Conference Paper
Algorithms and Experiments for Clique Relaxations—Finding Maximum s-Plexes
We propose new practical algorithms to find degree-relaxed variants of cliques called s-plexes. An s-plex denotes a vertex subset in a graph inducing a subgraph where every vertex has edges to all but at most s v...