GENERAL SPANNING TREES AND CORE LABELING

Yangjun Chen

2009

Abstract

The checking of graph reachability is an important opera¬tion in many applications, by which for two given nodes u and v in a directed graph G we will check whether u is reachable from v through a path in G or vice versa. In this paper, we focus ourselves on this issue. A new approach is proposed to compress transitive closure to support reach¬ability. The main idea is the concept of general spanning trees, as well as a new labeling technique, called core labeling. For a graph G with n nodes and e edges, the labeling time is bounded by O(n + e + tb), where t is the number of non-tree edges (edges that do not appear in the general spanning tree T of G) and b is the number of the leaf nodes of T. It can be proven that b equals G’s width, defined to be the size of a largest node subset U of G such that for every pair of nodes u, v  U, there does not exist a path from u to v or from v to u. The space and time com¬plexities are bounded by O(n + tb) and O(logb), respectively.

Paper Citation

in Harvard Style

Chen Y. (2009). GENERAL SPANNING TREES AND CORE LABELING . In Proceedings of the 4th International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-989-674-009-2, pages 93-98. DOI: 10.5220/0002238500930098

in Bibtex Style

@conference{icsoft09,
author={Yangjun Chen},
title={GENERAL SPANNING TREES AND CORE LABELING},
booktitle={Proceedings of the 4th International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2009},
pages={93-98},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002238500930098},
isbn={978-989-674-009-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - GENERAL SPANNING TREES AND CORE LABELING
SN - 978-989-674-009-2
AU - Chen Y.
PY - 2009
SP - 93
EP - 98
DO - 10.5220/0002238500930098