NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
From MaRDI portal
Publication:860400
DOI10.1016/j.dam.2006.04.016zbMath1110.68111MaRDI QIDQ860400
Publication date: 9 January 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.016
computational complexity; approximation algorithm; graph theory; spanning tree; NP-hard; vertex ranking
90C35: Programming involving graphs or networks
68R10: Graph theory (including graph drawing) in computer science
90C59: Approximation methods and heuristics in mathematical programming
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- On an edge ranking problem of trees and graphs
- Optimal node ranking of trees
- On a graph partition problem with application to VLSI layout
- Edge ranking of graphs is hard
- Optimal node ranking of tree in linear time
- Optimal edge ranking of trees in polynomial time
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- On Minimum Edge Ranking Spanning Trees
- Rankings of Graphs