Explicit construction of linear sized tolerant networks (Q1110541): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Noga Alon / rank | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Property / reviewed by | |||
Property / reviewed by: David P. Brown / rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q105583521 / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Noga Alon / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: David P. Brown / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eigenvalues and expanders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On size Ramsey number of paths, trees, and circuits. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3937444 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Universal Graphs for Spanning Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3900124 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On sparse graphs with dense long paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The size Ramsey number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Expanding graphs contain all small trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Size Ramsey numbers involving stars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3903002 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Graph Model for Fault-Tolerant Computing Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramanujan graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamiltonian circuits in random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3313788 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: MinimumK-hamiltonian graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(88)90189-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1998400388 / rank | |||
Normal rank |
Latest revision as of 10:00, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Explicit construction of linear sized tolerant networks |
scientific article |
Statements
Explicit construction of linear sized tolerant networks (English)
0 references
1988
0 references
A problem occurring in the study of fault tolerant linear arrays is the construction of a graph with the minimum number of vertices and edges such that after removing all but \(\epsilon\) portion of its vertices or edges, the remaining graph contains a path of some specified length. Suppose \(\epsilon >0\) and m is any integer, \(m\geq 1\). The authors present an explicit construction of graphs G with O(m/\(\epsilon)\) vertices and maximum degree \(O(1/\epsilon^ 2)\) such that after deleting all but \(\epsilon\)-portion of its vertices or edges, the remaining graph contains a path of length m.
0 references
fault tolerant linear arrays
0 references
minimum number
0 references
construction of graphs
0 references
path of length m
0 references