A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor
AuthorReed, B; Wood, DR
Source TitleACM Transactions on Algorithms
PublisherASSOC COMPUTING MACHINERY
University of Melbourne Author/sWOOD, DAVID
AffiliationMathematics and Statistics
Document TypeJournal Article
CitationsReed, B. & Wood, D. R. (2009). A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor. ACM TRANSACTIONS ON ALGORITHMS, 5 (4), https://doi.org/10.1145/1597036.1597043.
Access StatusThis item is currently not available from this repository
Let G be an n -vertex m -edge graph with weighted vertices. A pair of vertex sets A , B ⊆ V ( G ) is a 2/3 -separation of order | A ∩ B | if A ∪ B = V ( G ), there is no edge between A − B and B − A , and both A − B and B − A have weight at most 2/3 the total weight of G . Let ℓ ∈ Z + be fixed. Alon et al.  presented an algorithm that in O ( n 1/2 m ) time, outputs either a K ℓ -minor of G , or a separation of G of order O ( n 1/2 ). Whether there is a O ( n + m )-time algorithm for this theorem was left as an open problem. In this article, we obtain a O ( n + m )-time algorithm at the expense of a O ( n 2/3 ) separator. Moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. In particular, for any given ϵ ∈ [0,1/2], our algorithm outputs either a K ℓ -minor of G , or a separation of G with order O ( n (2−ϵ)/3 in O ( n 1 + ϵ + m ) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no K ℓ-minor.
KeywordsComputation Theory and Mathematics
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References