Augmenting weighted graphs to establish directed point-to-point connectivity

Mehdy Roayaei and Mohammadreza Razzazi ()
Additional contact information
Mehdy Roayaei: AmirKabir University of Technology
Mohammadreza Razzazi: AmirKabir University of Technology

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 15, 1030-1056

Abstract: Abstract 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 = s 1 , t 1 , … , s p , t p , 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.

Keywords: Graph augmentation; Point-to-point connectivity; Fixed-parameter tractability; Directed Steiner network; Parameterized algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0023-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:3:d:10.1007_s10878-016-0023-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0023-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().