21 Result(s)
within
Conference Paper
Manuel Sorge
-
Chapter and Conference Paper
The Complexity of Cluster Vertex Splitting and Company
Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges ...
-
Chapter and Conference Paper
Planarizing Graphs and Their Drawings by Vertex Splitting
The splitting number of a graph \(G=(V,E)\) G = ...
-
Chapter and Conference Paper
Constant Congestion Brambles in Directed Graphs
The Directed Grid Theorem, stating that there is a function f such that a directed graph of directed treewidth at least f(k) contains a directed grid of size at least k as a butterfly minor, after being a conject...
-
Chapter and Conference Paper
On (Coalitional) Exchange-Stable Matching
We study , which Alcalde [Economic Design, 1995] introduced as an alternative solution concept for matching markets involving property rights, such as assigning persons to ...
-
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...
-
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 ...
