A Heuristic Algorithm for Small Separators in Arbitrary Graphs

DOI10.1137/0219018MaRDI QIDQ3474888zbMATH OpenOpenAlexFDO

Authors David A. Plaisted

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219018

zbMATH Keywords

flows in networksrandom algorithmsseparators in graphs

Mathematics Subject Classification ID

Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Recommendations

• scientific article; zbMATH DE number 16297
• Planar Separators
• Finding small balanced separators
• A near optimal algorithm for edge separators (preliminary version)
• A separator theorem for graphs of bounded genus

Cited in

(14)

• Finding good approximate vertex and edge partitions is NP-hard
• Genetic algorithm based heuristics for the mapping problem
• General variable neighborhood search for computing graph separators
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Genetic search algorithms and their randomized operators
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• A near optimal algorithm for edge separators (preliminary version)
• Finding small balanced separators
• Finding small separators in linear time via treewidth reduction
• scientific article; zbMATH DE number 432835 (Why is no real title available?)
• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• scientific article; zbMATH DE number 1569023 (Why is no real title available?)
• A new lower bound on the size of the smallest vertex separator of a graph

This page was built for publication: A Heuristic Algorithm for Small Separators in Arbitrary Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474888)