An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
Summary :
The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1019-1026
- Publication Date
- 2003/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shin-ichi NAKAYAMA, Shigeru MASUYAMA, "An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 5, pp. 1019-1026, May 2003, doi: .
Abstract: The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1019/_p
Copy
@ARTICLE{e86-a_5_1019,
author={Shin-ichi NAKAYAMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs},
year={2003},
volume={E86-A},
number={5},
pages={1019-1026},
abstract={The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1019
EP - 1026
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.
ER -
English
