The complexity of testing whether a graph is a superconcentrator

DOI10.1016/0020-0190(81)90050-8zbMath0482.05059DBLPjournals/ipl/BlumKVPY81OpenAlexW1968864043WikidataQ97309514 ScholiaQ97309514MaRDI QIDQ1162529

Christos H. Papadimitriou, Mihalis Yannakakis, O. Vornberger, Richard M. Karp

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

zbMATH Keywords

NP-completenesssuperconcentratorconcentrator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (13)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superconcentrators
• On Representatives of Subsets
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: The complexity of testing whether a graph is a superconcentrator