5 Result(s)
-
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
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 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
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...
