NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem

DOI10.1016/j.dam.2006.04.016zbMath1110.68111OpenAlexW2125607890MaRDI QIDQ860400

N. E. Zubov

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

zbMATH Keywords

computational complexityapproximation algorithmgraph theoryspanning treeNP-hardvertex ranking

Mathematics Subject Classification ID

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