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.68111OpenAlexW2125607890MaRDI 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
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
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
This page was built for publication: NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem