Computing the isoperimetric number of a graph

DOI10.1007/BF02366479zbMath0835.05041MaRDI QIDQ1905161

Petr A. Golovach

Publication date: 8 February 1996

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

zbMATH Keywords

NP-hard problemisoperimetric number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items (2)

Maximum rooted connected expansion ⋮ Lit-only sigma game on a line graph

Cites Work

• Unnamed Item
• Unnamed Item
• On the bipartition of graphs
• Isoperimetric inequalities and Markov chains
• Isoperimetric inequalities, growth, and the spectrum of graphs
• Some simplified NP-complete graph problems
• Isoperimetric numbers of graphs
• The Spectral Radius of infinite Graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks

This page was built for publication: Computing the isoperimetric number of a graph