Improved Approximation Algorithms for Minimum Weight Vertex Separators
From MaRDI portal
Publication:3624379
DOI10.1137/05064299XzbMath1172.68063OpenAlexW2076164610MaRDI QIDQ3624379
James R. Lee, Mohammad Taghi Hajiaghayi, Uriel Feige
Publication date: 30 April 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/05064299x
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, Linear kernels for separating a graph into components of bounded size, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Computing Tree Decompositions, An Improvement of Reed’s Treewidth Approximation, Continuous quadratic programming formulations of optimization problems on graphs, Approximate tree decompositions of planar graphs in linear time, Fixed-Parameter Tractability of Treewidth and Pathwidth, Treewidth computation and extremal combinatorics, Chasing a Fast Robber on Planar Graphs and Random Graphs, Space saving by dynamic algebraization based on tree-depth, Approximation Algorithms for Euler Genus and Related Problems, Approximation and Kernelization for Chordal Vertex Deletion, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Treelength of series-parallel graphs, Approximating Pathwidth for Graphs of Small Treewidth, Tangle bases: Revisited, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, Practical algorithms for branch-decompositions of planar graphs, Fission: Practical algorithms for computing minimum balanced node separators, Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Treewidth versus clique number. II: Tree-independence number, Operational causality -- necessarily sufficient and sufficiently necessary, Unnamed Item, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Space efficient algorithm for solving reachability using tree decomposition and separators, Unnamed Item, Local search: is brute-force avoidable?, Typical sequences revisited -- computing width parameters of graphs, Unnamed Item, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Graph Clustering using Effective Resistance, Approximation algorithms for digraph width parameters, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Approximate Turing Kernelization for Problems Parameterized by Treewidth, Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery, An improvement of Reed's treewidth approximation, On Algorithms Employing Treewidth for $L$-bounded Cut Problems, Target set selection for conservative populations, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, A multilevel bilinear programming algorithm for the vertex separator problem, On classes of graphs with strongly sublinear separators, Applications of a New Separator Theorem for String Graphs, Near-Optimal Separators in String Graphs, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, On the $AC^0$ Complexity of Subgraph Isomorphism, To Approximate Treewidth, Use Treelength!, Unnamed Item, Unnamed Item, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Rank-width and tree-width of \(H\)-minor-free graphs, Contraction obstructions for treewidth, Unnamed Item, Hitting Forbidden Minors: Approximation and Kernelization, A $c^k n$ 5-Approximation Algorithm for Treewidth, Relaxations of Combinatorial Problems Via Association Schemes, Quasimetric embeddings and their applications, Lower bounds for treewidth of product graphs, A node-capacitated Okamura-Seymour theorem, Short Regular Expressions from Finite Automata: Empirical Results, Multicommodity flows and cuts in polymatroidal networks, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Partitioning a graph into small pieces with applications to path transversal, Algorithms and complexity for Turaev-Viro invariants, Improved Bounds for the Excluded-Minor Approximation of Treedepth, Separators in region intersection graphs, Finding small-width connected path decompositions in polynomial time, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, On the Tree-Width of Planar Graphs, Separator-based graph embedding into multidimensional grids with small edge-congestion, Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Unnamed Item
