Fixed parameter tractability of a biconnected bottleneck Steiner network problem

DOI10.1002/net.21926zbMath1528.68149OpenAlexW3002234683WikidataQ126331507 ScholiaQ126331507MaRDI QIDQ6066052

Charl J. Ras

Publication date: 15 November 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11343/275283

zbMATH Keywords

approximation algorithmsfixed-parameter tractabilitygeometric network2-connectivitybiconnected networkbottleneck Steiner network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)
• An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Approximations for a bottleneck Steiner tree problem
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• Bounding component sizes of two-connected Steiner networks
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• Exact Algorithms for the Bottleneck Steiner Tree Problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Bottleneck Steiner trees in the plane
• Minimally 2-connected graphs.
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Fixed parameter tractability of a biconnected bottleneck Steiner network problem