Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Theory of computation → Routing and network design problems"'
Autor:
Chekuri, Chandra, Jain, Rhea
Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::96fa25b96108e679a3890e48077d444c
We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a $2$-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximatio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c969014c22b45139846fdc8bbd99da1f
Autor:
Friggstad, Zachary, Mousavi, Ramin
We present an O(log k)-approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where k is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree, in which we get a O
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a40c485a276367a65bbafa5372063a97
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges whi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c1c11c1615314153237457ef5c1db8d
This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d492518829aec101a6e4d9d05162077e
http://arxiv.org/abs/2211.12431
http://arxiv.org/abs/2211.12431
Autor:
Chalermsook, Parinya, Huang, Chien-Chung, Nanongkai, Danupon, Saranurak, Thatchaphol, Sukprasert, Pattara, Yingchareonthawornchai, Sorrachai
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs)
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.37⟩
Chalermsook, P, Huang, C C, Nanongkai, D, Saranurak, T, Sukprasert, P & Yingchareonthawornchai, S 2022, Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver . in M Bojanczyk, E Merelli & D P Woodruff (eds), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 ., 37, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022, Paris, France, 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.37
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.37⟩
Chalermsook, P, Huang, C C, Nanongkai, D, Saranurak, T, Sukprasert, P & Yingchareonthawornchai, S 2022, Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver . in M Bojanczyk, E Merelli & D P Woodruff (eds), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 ., 37, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022, Paris, France, 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.37
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a min
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::75475875cb8c2675c448c436ff53f0ec
https://hal.science/hal-04044666
https://hal.science/hal-04044666
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. T
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c25c375ff28dc3639bec9469b9e4701
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs), 224
38th International Symposium on Computational Geometry
38th International Symposium on Computational Geometry
In the longest plane spanning tree problem, we are given a finite planar point set P, and our task is to find a plane (i.e., noncrossing) spanning tree TOPT for P with maximum total Euclidean edge length |TOPT|. Despite more than two decades of resea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1928e2f82166977038fede1d6c6544f1
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem (k-ECSS), as well as nonuniform demands such as
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c1ecf716344c02ce8b614c1f5535522
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs), 227
The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k - 1 edges of the graph may fail. We extend the simple uniform f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3537561a0c7e9717067933f94e555aa8
https://hdl.handle.net/20.500.11850/557702
https://hdl.handle.net/20.500.11850/557702