Cover Image

On the twin-width of near-regular graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Heinrich, Irene, Ihringer, Ferdinand, Raßmann, Simon, Volk, Lena
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Data Structures and Algorithms 68Q25, 68R10, 68R05 F.2.2; G.2.1; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
by: Bampis, Evripidis, et al.
Published: (2024)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

Experimental algorithms for the dualization problem
by: Mezzini, Mauro, et al.
Published: (2025)

Ordered Leaf Attachment (OLA) Vectors can Identify Reticulation Events even in Multifurcated Trees
by: Markin, Alexey, et al.
Published: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

A Constant-factor Approximation for Weighted Bond Cover
by: Kim, Eun Jung, et al.
Published: (2021)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets
by: Flores-Peñaloza, David, et al.
Published: (2024)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

Large cliques and large independent sets: can they coexist?
by: Feige, Uriel, et al.
Published: (2025)

Testing forbidden order-pattern properties on hypergrids
by: Chandramouleeswaran, Harish, et al.
Published: (2025)

Efficient Binary Decision Diagram Manipulation in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2021)

A Faster Algorithm for Independent Cut
by: Chernyshev, Vsevolod, et al.
Published: (2025)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
by: Oliveria, Mateus de Oliveira, et al.
Published: (2026)

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
by: Zhong, Xianghui
Published: (2019)