Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/31524
Title: Minimum activation cost node-disjoint paths in graphs with bounded treewidth
Authors: Alqahtani, Hasna Mohsen
Erlebach, Thomas
First Published: 2014
Presented at: 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014.
Publisher: Springer International Publishing
Citation: 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8327 LNCS, pp. 65-76
Abstract: In activation network problems we are given a directed or undirected graph G = (V,E) with a family {f uv : (u,v) ∈ E} of monotone non-decreasing activation functions from D2 to {0,1}, where D is a constant-size subset of the non-negative real numbers, and the goal is to find activation values xv for all v ∈ V of minimum total cost ∑  v ∈ V x v such that the activated set of edges satisfies some connectivity requirements. We propose algorithms that optimally solve the minimum activation cost of k node-disjoint st-paths (st-MANDP) problem in O(tw ((5 + tw)|D|)2tw + 2|V|3) time and the minimum activation cost of node-disjoint paths (MANDP) problem for k disjoint terminal pairs (s 1,t 1),…,(s k ,t k ) in O(tw ((4 + 3tw)|D|)2tw + 2|V|) time for graphs with treewidth bounded by tw.
DOI Link: 10.1007/978-3-319-04298-5_7
ISSN: 0302-9743
eISSN: 1611-3349
Links: http://link.springer.com/chapter/10.1007%2F978-3-319-04298-5_7
http://hdl.handle.net/2381/31524
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2014, Springer International Publishing. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
SOFSEM2014FinalAuthorVersion.pdfPost-review (final submitted)315.01 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.