Weighted graph separators and their applications

DOI10.1007/3-540-63397-9_11MaRDI QIDQ826080zbMATH OpenOpenAlexFDO

Authors Hristo N. Djidjev

Publication date 20 December 2021

Full work available at URL https://doi.org/10.1007/3-540-63397-9_11

zbMATH Keywords

binary treechordal graphplanar graphseparator theoremspanning tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Signed and weighted graphs (05C22)

Recommendations

• Partitioning planar graphs with vertex costs: Algorithms and applications
• Separators in graphs with negative and multiple vertex weights
• scientific article; zbMATH DE number 4064516
• Planar Separators
• Partitioning planar graphs with costs and weights

Cited in

(17)

• Separators in graphs with negative and multiple vertex weights
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Graph separators, with applications
• A near optimal algorithm for edge separators (preliminary version)
• Partitioning planar graphs with costs and weights
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• Planar Separators
• scientific article; zbMATH DE number 1953093 (Why is no real title available?)
• scientific article; zbMATH DE number 1926663 (Why is no real title available?)
• Object location using path separators
• NP-completeness of the Planar Separator Problems
• On weighted sublinear separators
• scientific article; zbMATH DE number 7692362 (Why is no real title available?)
• \(N\)-separators in planar graphs
• ETH-tight algorithm for cycle packing on unit disk graphs
• On cleaving a planar graph

This page was built for publication: Weighted graph separators and their applications

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