Cover Image

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Spalding-Jamieson, Jack
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
by: Lynch, Jayson, et al.
Published: (2025)

Simple Compact Monotone Tree Drawings
by: Oikonomou, Anargyros, et al.
Published: (2017)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
by: Hengeveld, Simon, et al.
Published: (2020)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

Upward Pointset Embeddings of Planar st-Graphs
by: Alegria, Carlos, et al.
Published: (2024)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
by: Yang, Puhan, et al.
Published: (2025)

Internally-Convex Drawings of Outerplanar Graphs in Small Area
by: Bekos, Michael A., et al.
Published: (2025)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
by: Madarasi, Péter
Published: (2025)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
by: Bentert, Matthias, et al.
Published: (2025)

An algorithm for accurate and simple-looking metaphorical maps
by: Katsanou, Eleni, et al.
Published: (2025)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
by: Di Battista, Giuseppe, et al.
Published: (2021)

Freeze-Tag in $L_1$ has Wake-up Time Five
by: Bonichon, Nicolas, et al.
Published: (2024)

Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
by: Förster, Henry, et al.
Published: (2023)

O(1)-Distortion Planar Emulators for String Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
by: Gribanov, D., et al.
Published: (2023)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
by: Antony, Dhanyamol, et al.
Published: (2023)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

The Complexity of Cluster Vertex Splitting and Company
by: Firbas, Alexander, et al.
Published: (2023)

Implicit representations via the polynomial method
by: Cardinal, Jean, et al.
Published: (2026)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
by: Elbassioni, Khaled
Published: (2025)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

Algorithmic Results for Weak Roman Domination Problem in Graphs
by: Paul, Kaustav, et al.
Published: (2024)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)