### 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.

Original language | English |
---|---|

Pages (from-to) | 2357-2363 |

Number of pages | 7 |

Journal | IEICE Transactions on Information and Systems |

Volume | E89-D |

Issue number | 8 |

DOIs | |

Publication status | Published - Aug 2006 |

### Fingerprint

### Keywords

- Algorithm
- Outerplanar graph
- Spanning tree
- Vertex ranking