Locally connected spanning trees on graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$. The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.
14 pages, 3 figures

Keywords

Data Structures and Algorithms, Discrete Mathematics, F.2.2; G.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32326

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0409013
 http://arxiv.org/abs/cs/0409013

Collections

arXiv