Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs

DOI10.1016/0196-6774(87)90042-3zbMath0633.68023OpenAlexW2019834939MaRDI QIDQ3771606

Thomas Lengauer

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90042-3

zbMATH Keywords

efficient algorithmsminimum spanning forestsdesign of VLSI circuitshierarchically defined graphs

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)

Related Items

Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Algorithms for graph problems on BNLC structured garphs, The complexity of approximating PSPACE-complete problems for hierarchical specifications, On matroids and hierarchical graphs, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Hierarchically specified unit disk graphs, Complexity of path-forming games, On matroids and hierarchical graphs, Hierarchically specified unit disk graphs, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs