Image de couverture de livre

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bourneuf, Romain, Planken, Tim
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
par: Bourneuf, Romain, et autres
Publié: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
par: Bourneuf, Romain, et autres
Publié: (2024)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
par: Bourneuf, Romain, et autres
Publié: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
par: Ghanbari, Babak, et autres
Publié: (2026)

Optimal and Efficient Partite Decompositions of Hypergraphs
par: Krapivin, Andrew, et autres
Publié: (2025)

Induced Minors and Coarse Tree Decompositions
par: Chudnovsky, Maria, et autres
Publié: (2026)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
par: Bandyapadhyay, Sayan, et autres
Publié: (2024)

A Uniformly Random Solution to Algorithmic Redistricting
par: Cai, Jin-Yi, et autres
Publié: (2024)

On The Maximum Linear Arrangement Problem for Trees
par: Alemany-Puig, Lluís, et autres
Publié: (2023)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
par: Iwata, Satoru, et autres
Publié: (2024)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
par: Paschalidis, Phevos, et autres
Publié: (2023)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
par: Jana, Satyabrata, et autres
Publié: (2025)

Computing Treedepth Obstructions
par: Kühn, Kolja
Publié: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
par: Shakeri, Heman, et autres
Publié: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
par: de Berg, Mark, et autres
Publié: (2024)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
par: Kita, Nanano
Publié: (2025)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
par: Chakraborty, Dibyayan, et autres
Publié: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
par: Holtgrefe, Niels, et autres
Publié: (2024)

Computational Verification of the Buratti--Horak--Rosa Conjecture for Small Integers and Inductive Approaches
par: Naik, Ranjan N
Publié: (2025)

Sampling Balanced Forests of Grids in Polynomial Time
par: Cannon, Sarah, et autres
Publié: (2023)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
par: Ameli, Afrouz Jabal, et autres
Publié: (2026)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
par: Hellmuth, Marc, et autres
Publié: (2023)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
par: Kunisky, Dmitriy, et autres
Publié: (2023)

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
par: Chen, Yeyuan
Publié: (2024)

A characterization of testable hypergraph properties
par: Joos, Felix, et autres
Publié: (2017)

A logarithmic approximation of linearly ordered colourings
par: Håstad, Johan, et autres
Publié: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
par: Bernshteyn, Anton, et autres
Publié: (2024)

A new width parameter of graphs based on edge cuts: $α$-edge-crossing width
par: Chang, Yeonsu, et autres
Publié: (2023)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
par: Deák, Bence, et autres
Publié: (2025)

The Strong Birthday Problem Revisited
par: Tripathy, Chijul B.
Publié: (2025)

Reconfiguration of List Colourings
par: Cambie, Stijn, et autres
Publié: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
par: Chakraborty, Dibyayan, et autres
Publié: (2025)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
par: Ghanbari, Babak, et autres
Publié: (2025)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
par: Torres, Ethan, et autres
Publié: (2025)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
par: An, Shinwoo, et autres
Publié: (2025)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
par: Shook, James M., et autres
Publié: (2025)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
par: Deligkas, Argyrios, et autres
Publié: (2025)

Parameterised algorithms for temporally satisfying reconfiguration problems
par: Davot, Tom, et autres
Publié: (2025)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
par: Bencs, Ferenc, et autres
Publié: (2025)

Interval H-graphs : Recognition and forbidden obstructions
par: Müller, Haiko, et autres
Publié: (2025)