NP-hardness and fixed-parameter tractability of the minimum spanner problem
type: Item
instance of: scholarly article
title: NP-hardness and fixed-parameter tractability of the minimum spanner problem
zbMATH Open document ID: 1401.68098
author: Yusuke Kobayashi
published in: Theoretical Computer Science
publication date: 2018-09-27T00:00:00Z
full work available at URL: http://hdl.handle.net/2433/244837
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6944702
zbMATH Keywords: minimum spanner problem
zbMATH Keywords: planar graphs
zbMATH Keywords: degree-bounded graphs
zbMATH Keywords: NP-hardness
zbMATH Keywords: FPT algorithm
MaRDI profile type: Publication
OpenAlex ID: W2810702411
cites work: The 4/3 Additive Spanner Exponent Is Tight
cites work: Q4373672
cites work: NP-completeness of minimum spanner problems
cites work: Tree Spanners
cites work: Spanners in graphs of bounded degree
cites work: New Additive Spanners
cites work: Near-Optimal Light Spanners
cites work: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
cites work: Polylog-time and near-linear work approximation scheme for undirected shortest paths
cites work: Compact roundtrip routing in directed networks
cites work: Q3577833
cites work: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
cites work: Computing almost shortest paths
cites work: Q4198056
cites work: Tree 3-spanners on interval, permutation and regular bipartite graphs
cites work: Graph spanners
cites work: An Optimal Synchronizer for the Hypercube
cites work: A trade-off between space and efficiency for routing tables
cites work: Approximate distance oracles
cites work: Restrictions of minimum spanner problems
DOI: 10.1016/J.TCS.2018.06.031
description: scientific article; zbMATH DE number 6944702