A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jaffke, Lars, de Lima, Paloma T., Nadara, Wojciech, Sam, Emmanuel
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity 05C85
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
by: Baste, Julien, et al.
Published: (2019)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
by: Bojikian, Narek, et al.
Published: (2025)

Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
by: Bojikian, Narek, et al.
Published: (2025)

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
by: Kokai, Toranosuke, et al.
Published: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
by: Bougeret, Marin, et al.
Published: (2024)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
by: Bojikian, Narek, et al.
Published: (2024)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
by: Quanrud, Kent, et al.
Published: (2025)

The Complexity of Distance-$r$ Dominating Set Reconfiguration
by: Banerjee, Niranka, et al.
Published: (2023)

On the parameterized complexity of computing good edge-labelings
by: de Andrade, Davi, et al.
Published: (2024)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
by: Bojikian, Narek, et al.
Published: (2023)

Finding Diverse Solutions Parameterized by Cliquewidth
by: Drabik, Karolina, et al.
Published: (2024)

Steiner Tree Parameterized by Multiway Cut and Even Less
by: Jansen, Bart M. P., et al.
Published: (2024)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

$t$-sails and sparse hereditary classes of unbounded tree-width
by: Cocks, Daniel
Published: (2023)

Kernelization dichotomies for hitting minors under structural parameterizations
by: Bougeret, Marin, et al.
Published: (2025)

Dynamic programming on bipartite tree decompositions
by: Jaffke, Lars, et al.
Published: (2023)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

A simple quadratic kernel for Token Jumping on surfaces
by: Cranston, Daniel W., et al.
Published: (2024)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
by: Nasre, Meghana, et al.
Published: (2023)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
by: Liao, I-Cheng, et al.
Published: (2023)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
by: Jelínek, Vít, et al.
Published: (2020)

Improved Outerplanarity Bounds for Planar Graphs
by: Biedl, Therese, et al.
Published: (2024)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

A practical algorithm for 2-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
by: Bodlaender, Hans L., et al.
Published: (2026)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
by: Bai, Tian, et al.
Published: (2026)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)