Augmenting weighted graphs to establish directed point-to-point connectivity
| Autor: | Mehdy Roayaei, Mohammadreza Razzazi |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies Comparability graph Minimum weight Parameterized complexity 0102 computer and information sciences 02 engineering and technology Directed graph Directed acyclic graph 01 natural sciences Feedback arc set Computer Science Applications Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Path (graph theory) Discrete Mathematics and Combinatorics Level structure MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 33:1030-1056 |
| ISSN: | 1573-2886 1382-6905 |
| Popis: | We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices $$P=\left\{ {\left( {s_1 ,t_1 } \right) ,\ldots ,\left( {s_p ,t_p } \right) } \right\} $$P=s1,t1,ź,sp,tp, one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present some parameterized algorithms and parameterized complexity results for it. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink