Image de couverture de livre

Tight Bounds for some Classical Problems Parameterized by Cutwidth

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bojikian, Narek, Chekan, Vera, Kratsch, Stefan
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms 05C85 F.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
par: Bojikian, Narek, et autres
Publié: (2025)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
par: Bojikian, Narek, et autres
Publié: (2024)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
par: Bojikian, Narek, et autres
Publié: (2023)

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
par: Bergougnoux, Benjamin, et autres
Publié: (2026)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Finding Diverse Solutions Parameterized by Cliquewidth
par: Drabik, Karolina, et autres
Publié: (2024)

Steiner Tree Parameterized by Multiway Cut and Even Less
par: Jansen, Bart M. P., et autres
Publié: (2024)

Improved Outerplanarity Bounds for Planar Graphs
par: Biedl, Therese, et autres
Publié: (2024)

A practical algorithm for 2-admissibility
par: Awofeso, Christine, et autres
Publié: (2025)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
par: Jaffke, Lars, et autres
Publié: (2025)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
par: Bougeret, Marin, et autres
Publié: (2024)

Finding Diverse Minimum s-t Cuts
par: de Berg, Mark, et autres
Publié: (2023)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
par: Agrawal, Akanksha, et autres
Publié: (2024)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
par: Gartland, Peter, et autres
Publié: (2023)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
par: Bonnet, Édouard, et autres
Publié: (2023)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
par: Quanrud, Kent, et autres
Publié: (2025)

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
par: Kokai, Toranosuke, et autres
Publié: (2025)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
par: Atherton, William, et autres
Publié: (2024)

On the Complexity of the Bilevel Shortest Path Problem
par: Henke, Dorothee, et autres
Publié: (2024)

Kernelization dichotomies for hitting minors under structural parameterizations
par: Bougeret, Marin, et autres
Publié: (2025)

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

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
par: Masařík, Tomáš, et autres
Publié: (2026)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
par: Krishnaswamy, Ravishankar, et autres
Publié: (2014)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
par: Patzner, Julian, et autres
Publié: (2024)

Correlation Clustering with Vertex Splitting
par: Bentert, Matthias, et autres
Publié: (2024)

Shortest two disjoint paths in conservative graphs
par: Schlotter, Ildikó
Publié: (2023)

$t$-sails and sparse hereditary classes of unbounded tree-width
par: Cocks, Daniel
Publié: (2023)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
par: Baste, Julien, et autres
Publié: (2019)

The Complexity of Distance-$r$ Dominating Set Reconfiguration
par: Banerjee, Niranka, et autres
Publié: (2023)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
par: Sau, Ignasi, et autres
Publié: (2024)

Traffic-Oblivious Multi-Commodity Flow Network Design
par: Chimani, Markus, et autres
Publié: (2025)

A simple quadratic kernel for Token Jumping on surfaces
par: Cranston, Daniel W., et autres
Publié: (2024)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
par: Bojikian, Narek, et autres
Publié: (2025)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
par: Oum, Sang-il, et autres
Publié: (2026)

Cluster deletion and clique partitioning in graphs with bounded clique number
par: Galesi, Nicola, et autres
Publié: (2025)

Tree-independence number VI. Thetas and pyramids
par: Chudnovsky, Maria, et autres
Publié: (2025)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
par: Nasre, Meghana, et autres
Publié: (2023)

Temporalizing digraphs via linear-size balanced bi-trees
par: Bessy, Stéphane, et autres
Publié: (2023)

Identification to Subclasses of Chordal Graphs
par: Golovach, Petr A., et autres
Publié: (2026)

Exact Algorithms for MaxCut on Split Graphs
par: Lalovic, Marko
Publié: (2024)