Shallow grates
type: Item
instance of: scholarly article
title: Shallow grates
zbMATH Open document ID: 0791.05047
DOI: 10.1016/0304-3975(94)90135-X
author: Maria M. Klawe
published in: Theoretical Computer Science
publication date: 1994-02-22T00:00:00Z
review text: This note gives a construction for a family of weak grates; that is, acyclic digraphs of logarithmic depth with this property: A superlinear number of pairs of vertices remain connected after removing any sufficiently small linear sized vertex set. The construction is based on one by Schnitger for acyclic digraphs with a similar property. Schnitger's graphs are modified by replacing vertices and edges by appropriate vertex sets and edge sets. The construction easily generalizes to digraphs of arbitrary depth.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 501199
zbMATH Keywords: grates
zbMATH Keywords: acyclic digraphs
zbMATH Keywords: Schnitger's graphs
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: A lower bound on the area of permutation layouts
cites work: Sorting in \(c \log n\) parallel steps
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: On sparse graphs with dense long paths
cites work: Expanding graphs contain all small trees
cites work: Explicit constructions of linear-sized superconcentrators
cites work: New lower bound techniques for VLSI
cites work: Q4385520
cites work: How to share memory in a distributed system
cites work: Q4164821
full work available at URL: 0304-3975(94)90135-x
OpenAlex ID: W2913852242
Recommended article: The pointfree version of grills
Recommended article: Sandwich plates of minimal compliance
Recommended article: On the convergence and adherence of grills
Recommended article: Q3099980
Recommended article: Grain filters
Recommended article: Q4279117
description: scientific article; zbMATH DE number 501199