NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
type: Item
instance of: scholarly article
title: NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
zbMATH Open document ID: 1110.68111
author: N. E. Zubov
published in: Discrete Applied Mathematics
publication date: 2007-01-09T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 5083147
zbMATH Keywords: vertex ranking
zbMATH Keywords: spanning tree
zbMATH Keywords: graph theory
zbMATH Keywords: NP-hard
zbMATH Keywords: computational complexity
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2006.04.016
OpenAlex ID: W2125607890
cites work: Rankings of Graphs
cites work: On the vertex ranking problem for trapezoid, circular-arc and other graphs
cites work: Optimal node ranking of trees
cites work: On an edge ranking problem of trees and graphs
cites work: Edge ranking of graphs is hard
cites work: Q4250211
cites work: On minimum edge ranking spanning trees
cites work: Optimal node ranking of tree in linear time
cites work: On a graph partition problem with application to VLSI layout
cites work: Optimal edge ranking of trees in polynomial time
DOI: 10.1016/J.DAM.2006.04.016
description: scientific article; zbMATH DE number 5083147