Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
View through CrossRef
Given a set of weighted directed paths in a bidirected tree, the maximum weight edge-disjoint paths problem (MWEDP) is to select a subset of the given paths such that the selected paths are edge-disjoint and the total weight of the selected paths is maximized. MWEDP is
NP
- hard for bidirected trees of unbounded degree, even if all weights are the same (the unweighted case). Three different approximation algorithms are implemented: a known combinatorial (5/3 + ε)-approximation algorithm
A
1
for the unweighted case, a new combinatorial 2-approximation algorithm
A
2
for the weighted case, and a known (5/3 + ε)-approximation algorithm
A
3
for the weighted case that is based on linear programming. For algorithm
A
1
, it is shown how efficient data structures can be used to obtain a worst-case running-time of
O(m + n + 4
1/ε
√n ċ m)
for instances consisting of
m
paths in a tree with
n
nodes. Experimental results regarding the running-times and the quality of the solutions obtained by the three approximation algorithms are reported. Where possible, the approximate solutions are compared to the optimal solutions, which were computed by running CPLEX on an integer linear programming formulation of MWEDP.
Association for Computing Machinery (ACM)
Title: Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
Description:
Given a set of weighted directed paths in a bidirected tree, the maximum weight edge-disjoint paths problem (MWEDP) is to select a subset of the given paths such that the selected paths are edge-disjoint and the total weight of the selected paths is maximized.
MWEDP is
NP
- hard for bidirected trees of unbounded degree, even if all weights are the same (the unweighted case).
Three different approximation algorithms are implemented: a known combinatorial (5/3 + ε)-approximation algorithm
A
1
for the unweighted case, a new combinatorial 2-approximation algorithm
A
2
for the weighted case, and a known (5/3 + ε)-approximation algorithm
A
3
for the weighted case that is based on linear programming.
For algorithm
A
1
, it is shown how efficient data structures can be used to obtain a worst-case running-time of
O(m + n + 4
1/ε
√n ċ m)
for instances consisting of
m
paths in a tree with
n
nodes.
Experimental results regarding the running-times and the quality of the solutions obtained by the three approximation algorithms are reported.
Where possible, the approximate solutions are compared to the optimal solutions, which were computed by running CPLEX on an integer linear programming formulation of MWEDP.
Related Results
2-Edge Connectivity in Directed Graphs
2-Edge Connectivity in Directed Graphs
Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been inv...
Improving the Reliability of Interconnection Networks Using Replicated 4-Disjoint GIN
Improving the Reliability of Interconnection Networks Using Replicated 4-Disjoint GIN
Today, high-performance computing is recognized as a necessity in various industries. The stable and secure connection between system components, such as CPUs and memories, require...
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
THE FORCING EDGE FIXING EDGE-TO-VERTEX MONOPHONIC NUMBER OF A GRAPH
For a connected graph G = (V, E), a set Se ⊆ E(G)–{e} is called an edge fixing edge-to-vertex monophonic set of an edge e of a connected graph G if every vertex of G lies on an e –...
The upper connected edge geodetic number of a graph
The upper connected edge geodetic number of a graph
For a non-trivial connected graph G, a set S ? V (G) is called an edge
geodetic set of G if every edge of G is contained in a geodesic joining some
pair of vertices in S. The...
The edge-to-edge geodetic domination number of a graph
The edge-to-edge geodetic domination number of a graph
Let G = (V, E) be a connected graph with at least three vertices. A set S Í E is called an edge-to-edge geodetic dominating set of G if S is both an edge-to-edge geodetic set of G ...
Geo‐information mapping improves Canny edge detection method
Geo‐information mapping improves Canny edge detection method
AbstractAiming at the shortcomings of the current Canny edge detection method in terms of noise removal, threshold setting, and edge recognition, this paper proposes a method for i...
Adaptive Learning and Mining for Data Streams and Frequent Patterns
Adaptive Learning and Mining for Data Streams and Frequent Patterns
Aquesta tesi està dedicada al disseny d'algorismes de mineria de dades per fluxos de dades que evolucionen en el temps i per l'extracció d'arbres freqüents tancats. Primer ens ocu...
Approximation Algorithms for Relative Survivable Network Design Problems
Approximation Algorithms for Relative Survivable Network Design Problems
Abstract
In the {\sc Survivable Network Design} ({\SND}) problem we seek a min-cost subgraph that satisfies pairwise edge-connectivity demands. This encompasses the {\sc $k...