Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem

DOI10.1007/s10878-018-00374-xzbMath1426.90244arXiv1801.10416OpenAlexW2963795223WikidataQ128641678 ScholiaQ128641678MaRDI QIDQ2424799

Mattia D'Emidio, Luca Forlizzi, Guido Proietti, Daniele Frigioni, Stefano Leucci

Publication date: 25 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.10416

zbMATH Keywords

network designapproximation algorithmshardnessfixed-parameter tractabilityclustered shortest-path tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items (4)

Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ A multifactorial optimization paradigm for linkage tree genetic algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for the clustered traveling salesman problem
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Generalized network design problems.
• On the clustered Steiner tree problem
• Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
• Finding disjoint dense clubs in a social network
• Improved Purely Additive Fault-Tolerant Spanners
• Fourier meets M\"{o}bius: fast subset convolution
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Steiner Tree Approximation via Iterative Randomized Rounding
• On \((s,t)\)-relaxed \(L(2,1)\)-labeling of graphs

This page was built for publication: Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem