Fault-Tolerant Meshes with Constant Degree

Toshinori YAMADA

doi:10.1093/ietfec/e88-a.4.935

Fault-Tolerant Meshes with Constant Degree

Toshinori YAMADA

Full Text Views

0

Cite this

Summary :

This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k^1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k^2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.4 pp.935-940

Publication Date: 2005/04/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.4.935

Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)

Category

Cite this

Copy

Toshinori YAMADA, "Fault-Tolerant Meshes with Constant Degree" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 4, pp. 935-940, April 2005, doi: 10.1093/ietfec/e88-a.4.935.
Abstract: This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k^1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k^2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.4.935/_p

Copy

@ARTICLE{e88-a_4_935,
author={Toshinori YAMADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fault-Tolerant Meshes with Constant Degree},
year={2005},
volume={E88-A},
number={4},
pages={935-940},
abstract={This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k^1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k^2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.},
keywords={},
doi={10.1093/ietfec/e88-a.4.935},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Fault-Tolerant Meshes with Constant Degree
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 935
EP - 940
AU - Toshinori YAMADA
PY - 2005
DO - 10.1093/ietfec/e88-a.4.935
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2005
AB - This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k^1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k^2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.
ER -