Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands
| Autor: | Colucci, Lucas, Erdős, Péter L., Győri, Ervin, Mezei, Tamás Róbert |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Theoretical Computer Science, Volume 775, 5 July 2019, Pages 16-25 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.tcs.2018.12.007 |
| Popis: | We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of $\Delta(D)$ which still guarantees that the demand graph $D$ has a realization in $K_{n,n}$. We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in $K_{n,n}$. Comment: 15 pages, draws from arXiv:1702.04313 |
| Databáze: | arXiv |
| Externí odkaz: |
|