11 Result(s)
within
Conference Paper
Manuel Sorge
Algorithm Analysis and Problem Complexity
Data Structures
-
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...
-
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
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
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 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
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
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
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...
