File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/17M1150633
- Scopus: eid_2-s2.0-85071487134
- WOS: WOS:000487856600020
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On Mergings in Acyclic Directed Graphs
Title | On Mergings in Acyclic Directed Graphs |
---|---|
Authors | |
Keywords | merging network flow theory graph structure |
Issue Date | 2019 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php |
Citation | SIAM Journal on Discrete Mathematics, 2019, v. 33 n. 3, p. 1482-1502 How to Cite? |
Abstract | Consider an acyclic directed graph $G$ with sources $s_1, s_2, ldots,s_n$ and sinks $r_1, r_2, ldots, r_n$. For $i=1, 2, ldots,n$, let $c_i$ denote the size of the minimum edge cut between $s_i$ and $r_i$, which, by Menger's theorem, implies that there exists a group of $c_i$ edge-disjoint paths from $s_i$ to $r_i$. Although they are edge disjoint within the same group, the above-mentioned edge-disjoint paths from different groups may merge with each other (or, roughly speaking, share a common subpath). In this paper we show that by choosing these paths appropriately, the number of mergings among all these edge-disjoint paths is always bounded by a finite function $mathcal{M}(c_1, c_2, ldots, c_n)$, which is independent of the size of $G$. Moreover, we prove some elementary properties of $mathcal{M}(c_1, c_2, dots, c_n)$, derive exact values of $mathcal{M}(1, c)$ and $mathcal{M}(2, c)$, and establish a scaling law of $mathcal{M}(c_1, c_2)$ when one of the parameters is fixed. |
Persistent Identifier | http://hdl.handle.net/10722/277238 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 1.031 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Han, G | - |
dc.date.accessioned | 2019-09-20T08:47:14Z | - |
dc.date.available | 2019-09-20T08:47:14Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | SIAM Journal on Discrete Mathematics, 2019, v. 33 n. 3, p. 1482-1502 | - |
dc.identifier.issn | 0895-4801 | - |
dc.identifier.uri | http://hdl.handle.net/10722/277238 | - |
dc.description.abstract | Consider an acyclic directed graph $G$ with sources $s_1, s_2, ldots,s_n$ and sinks $r_1, r_2, ldots, r_n$. For $i=1, 2, ldots,n$, let $c_i$ denote the size of the minimum edge cut between $s_i$ and $r_i$, which, by Menger's theorem, implies that there exists a group of $c_i$ edge-disjoint paths from $s_i$ to $r_i$. Although they are edge disjoint within the same group, the above-mentioned edge-disjoint paths from different groups may merge with each other (or, roughly speaking, share a common subpath). In this paper we show that by choosing these paths appropriately, the number of mergings among all these edge-disjoint paths is always bounded by a finite function $mathcal{M}(c_1, c_2, ldots, c_n)$, which is independent of the size of $G$. Moreover, we prove some elementary properties of $mathcal{M}(c_1, c_2, dots, c_n)$, derive exact values of $mathcal{M}(1, c)$ and $mathcal{M}(2, c)$, and establish a scaling law of $mathcal{M}(c_1, c_2)$ when one of the parameters is fixed. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php | - |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics | - |
dc.rights | SIAM Journal on Discrete Mathematics. Copyright © Society for Industrial and Applied Mathematics. | - |
dc.rights | © [2019] Society for Industrial and Applied Mathematics. First Published in [SIAM Journal on Discrete Mathematics] in [2019, v. 33 n. 33, p. 1482-1502], published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | merging | - |
dc.subject | network flow theory | - |
dc.subject | graph structure | - |
dc.title | On Mergings in Acyclic Directed Graphs | - |
dc.type | Article | - |
dc.identifier.email | Han, G: ghan@hku.hk | - |
dc.identifier.authority | Han, G=rp00702 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/17M1150633 | - |
dc.identifier.scopus | eid_2-s2.0-85071487134 | - |
dc.identifier.hkuros | 305686 | - |
dc.identifier.volume | 33 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 1482 | - |
dc.identifier.epage | 1502 | - |
dc.identifier.isi | WOS:000487856600020 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 0895-4801 | - |