The Undirected Optical Indices of Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916523701960704 |
|---|---|
| author | Lo, Yuan-Hsun Fu, Hung-Lin Zhang, Yijin Wong, Wing Shing |
| author_facet | Lo, Yuan-Hsun Fu, Hung-Lin Zhang, Yijin Wong, Wing Shing |
| contents | For a connected graph $G$, an instance $I$ is a set of pairs of vertices and a corresponding routing $R$ is a set of paths specified for all vertex-pairs in $I$. Let $\mathfrak{R}_I$ be the collection of all routings with respect to $I$. The undirected optical index of $G$ with respect to $I$ refers to the minimum integer $k$ to guarantee the existence of a mapping $ϕ:R\to\{1,2,\ldots,k\}$, such that $ϕ(P)\neqϕ(P')$ if $P$ and $P'$ have common edge(s), over all routings $R\in\mathfrak{R}_I$. A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let $w(G,I)$ and $π(G,I)$ denote the undirected optical index and edge-forwarding index with respect to $I$, respectively. In this paper, we derive the inequality $w(T,I_A)<\frac{3}{2}π(T,I_A)$ for any tree $T$, where $I_A:=\{\{x,y\}:\,x,y\in V(T)\}$ is the all-to-all instance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1808_09256 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | The Undirected Optical Indices of Trees Lo, Yuan-Hsun Fu, Hung-Lin Zhang, Yijin Wong, Wing Shing Combinatorics 05C05, 05C15, 05C90 For a connected graph $G$, an instance $I$ is a set of pairs of vertices and a corresponding routing $R$ is a set of paths specified for all vertex-pairs in $I$. Let $\mathfrak{R}_I$ be the collection of all routings with respect to $I$. The undirected optical index of $G$ with respect to $I$ refers to the minimum integer $k$ to guarantee the existence of a mapping $ϕ:R\to\{1,2,\ldots,k\}$, such that $ϕ(P)\neqϕ(P')$ if $P$ and $P'$ have common edge(s), over all routings $R\in\mathfrak{R}_I$. A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let $w(G,I)$ and $π(G,I)$ denote the undirected optical index and edge-forwarding index with respect to $I$, respectively. In this paper, we derive the inequality $w(T,I_A)<\frac{3}{2}π(T,I_A)$ for any tree $T$, where $I_A:=\{\{x,y\}:\,x,y\in V(T)\}$ is the all-to-all instance. |
| title | The Undirected Optical Indices of Trees |
| topic | Combinatorics 05C05, 05C15, 05C90 |
| url | https://arxiv.org/abs/1808.09256 |