A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs
Summary :
The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.8 pp.2357-2363
- Publication Date
- 2006/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.8.2357
- Type of Manuscript
- Special Section INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
- 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, "A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 8, pp. 2357-2363, August 2006, doi: 10.1093/ietisy/e89-d.8.2357.
Abstract: The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.8.2357/_p
Copy
@ARTICLE{e89-d_8_2357,
author={Shin-ichi NAKAYAMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs},
year={2006},
volume={E89-D},
number={8},
pages={2357-2363},
abstract={The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.},
keywords={},
doi={10.1093/ietisy/e89-d.8.2357},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2357
EP - 2363
AU - Shin-ichi NAKAYAMA
AU - Shigeru MASUYAMA
PY - 2006
DO - 10.1093/ietisy/e89-d.8.2357
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2006
AB - The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
ER -
English
