Cover Image

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bojikian, Narek, Kratsch, Stefan
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms 05C85 F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

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

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

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

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

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

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

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
by: Bergougnoux, Benjamin, et al.
Published: (2026)

Finding Diverse Minimum s-t Cuts
by: de Berg, Mark, et al.
Published: (2023)

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

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
by: Bonnet, Édouard, et al.
Published: (2023)

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

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

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

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)

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

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

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
by: Kratsch, Stefan
Published: (2026)

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

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
by: Jaffke, Lars, et al.
Published: (2025)

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

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
by: Masařík, Tomáš, et al.
Published: (2026)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
by: Krishnaswamy, Ravishankar, et al.
Published: (2014)

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

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

Correlation Clustering with Vertex Splitting
by: Bentert, Matthias, et al.
Published: (2024)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
by: Bojikian, Narek, et al.
Published: (2025)

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

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

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

On the Complexity of the Bilevel Shortest Path Problem
by: Henke, Dorothee, et al.
Published: (2024)

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

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
by: Dallard, Clément, 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)

TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
by: Dau, Son Hoang, et al.
Published: (2022)