Cover Image

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bojikian, Narek, Firbas, Alexander, Ganian, Robert, Hoang, Hung P., Szilágyi, Krisztina
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms 68Q27 F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

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

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

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

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

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

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
by: Jiang, Xinwen, et al.
Published: (2021)

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)

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

Parameterized Algorithms for Kidney Exchange
by: Maiti, Arnab, et al.
Published: (2021)

Sublinear-Time Computation in the Presence of Online Erasures
by: Kalemaj, Iden, et al.
Published: (2021)

Efficient Processing of Subsequent Densest Subgraph Query
by: Hung, Chia-Yang, et al.
Published: (2024)

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

On the Advice Complexity of Online Unit Clustering
by: Nagy-György, Judit
Published: (2023)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
by: Kullmann, Oliver, et al.
Published: (2026)

Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
by: Borodin, Allan, et al.
Published: (2025)

Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
by: Gu, Qian-Ping, et al.
Published: (2025)

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

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Shortest Paths without a Map, but with an Entropic Regularizer
by: Bubeck, Sébastien, et al.
Published: (2022)

Prediction-Augmented Mechanism Design for Weighted Facility Location
by: Shi, Yangguang, et al.
Published: (2025)

Parameterized Complexity of Efficient Sortation
by: Ganian, Robert, 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)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

Streaming algorithms for groups and semigroups
by: Lohrey, Markus, et al.
Published: (2022)

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond
by: Keil, J. Mark, et al.
Published: (2024)

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
by: AmaniHamedani, Alireza, et al.
Published: (2024)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

How to Compute a Moving Sum
by: Maslen, David K., et al.
Published: (2025)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
by: Goerigk, Marc, et al.
Published: (2026)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
by: Göbel, Andreas, et al.
Published: (2025)

Binary Tree Block Encoding of Classical Matrix
by: Li, Zexian, et al.
Published: (2025)

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
by: Gribelyuk, Elena, et al.
Published: (2024)