Cover Image

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Groenland, Carla, Nederlof, Jesper, Koana, Tomohiro
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
by: Björklund, Andreas, et al.
Published: (2023)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Determinantal Sieving
by: Eiben, Eduard, et al.
Published: (2023)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

Quasi-linear distance query reconstruction for graphs of bounded treelength
by: Bastide, Paul, et al.
Published: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
by: Sun, Ming, et al.
Published: (2022)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
by: Mahapatra, Sugyani, et al.
Published: (2021)

Improved exploration of temporal graphs
by: Bastide, Paul, et al.
Published: (2025)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

Cost-Distance Steiner Trees for Timing-Constrained Global Routing
by: Held, Stephan, et al.
Published: (2025)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Multi-Level Steiner Trees
by: Ahmed, Reyan, et al.
Published: (2018)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
by: Opler, Michal
Published: (2024)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

Optimal distance query reconstruction for graphs without long induced cycles
by: Bastide, Paul, et al.
Published: (2023)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)