[{"author":[{"last_name":"Kolman","first_name":"Petr"},{"last_name":"Scheideler","first_name":"Christian","id":"20792"}],"dini_type":"doc-type:conferenceObject","status":"public","citation":{"apa":"Kolman, P., & Scheideler, C. (2012). Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case. In *Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)* (pp. 800–810). https://doi.org/10.1137/1.9781611973099.64","mla":"Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case.” *Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)*, 2012, pp. 800–10, doi:10.1137/1.9781611973099.64.","bibtex":"@inproceedings{Kolman_Scheideler_2012, title={Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case}, DOI={10.1137/1.9781611973099.64}, booktitle={Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)}, author={Kolman, Petr and Scheideler, Christian}, year={2012}, pages={800–810} }","chicago":"Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case.” In *Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)*, 800–810, 2012. https://doi.org/10.1137/1.9781611973099.64.","ieee":"P. Kolman and C. Scheideler, “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case,” in *Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)*, 2012, pp. 800–810.","short":"P. Kolman, C. Scheideler, in: Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 800–810."},"has_accepted_license":"1","file_date_updated":"2018-03-15T06:35:58Z","dc":{"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1137/1.9781611973099.64"],"description":["Given an integer h, a graph G = (V;E) with arbitrary positive edge capacities and k pairs of vertices (s1; t1); (s2; t2); : : : ; (sk; tk), called terminals, an h-route cut is a set F µ E of edges such that after the removal of the edges in F no pair si ¡ ti is connected by h edge-disjoint paths (i.e., the connectivity of every si ¡ ti pair is at most h ¡ 1 in (V;E n F)). The h-route cut is a natural generalization of the classical cut problem for multicommodity °ows (take h = 1). The main result of this paper is an O(h722h log2 k)-approximation algorithm for the minimum h-route cut problem in the case that s1 = s2 = ¢ ¢ ¢ = sk, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicom-modity °ows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems."],"subject":["ddc:040"],"date":["2012"],"rights":["info:eu-repo/semantics/closedAccess"],"source":["Kolman P, Scheideler C. Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case. In: *Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)*. ; 2012:800-810. doi:10.1137/1.9781611973099.64"],"identifier":["https://ris.uni-paderborn.de/record/632"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"creator":["Kolman, Petr","Scheideler, Christian"],"title":["Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case"]},"abstract":[{"lang":"eng"}],"page":"800-810","creator":{"id":"15504","login":"florida"},"file":[{"relation":"main_file","access_level":"closed","content_type":"application/pdf","success":1,"file_id":"1234","file_size":220213,"date_created":"2018-03-15T06:35:58Z","date_updated":"2018-03-15T06:35:58Z","file_name":"632-SODA2012-Scheideler_01.pdf","creator":"florida"}],"date_created":"2017-10-17T12:42:55Z","type":"conference","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"publication":"Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)","user_id":"15504","uri_base":"https://ris.uni-paderborn.de","department":[{"tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}],"_id":"79"}],"ddc":[],"_id":"632","date_updated":"2022-01-06T07:03:01Z"}]