The complexity of testing whether a graph is a superconcentrator
From MaRDI portal
Publication:1162529
DOI10.1016/0020-0190(81)90050-8zbMath0482.05059OpenAlexW1968864043WikidataQ97309514 ScholiaQ97309514MaRDI QIDQ1162529
Christos H. Papadimitriou, Mihalis Yannakakis, O. Vornberger, Richard M. Karp, Manuel Blum
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(81)90050-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
Multi-processor scheduling and expanders, Eigenvalues and expanders, Isoperimetric inequalities in simplicial complexes, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Expander graphs and their applications, Finding Critical Links for Closeness Centrality, The symbiotic relationship of combinatorics and matrix theory, Computation of best possible low degree expanders, The complexity of explicit constructions, Highly symmetric expanders, Minimal selectors and fault tolerant networks, NONEXISTENCE OF A CIRCULANT EXPANDER FAMILY, Combinatorial analysis (nonnegative matrices, algorithmic problems)
Cites Work
