FINDING PATHS AND DELETING EDGES IN DIRECTED ACYCLIC GRAPHS

被引：57

作者：

ITALIANO, GF

机构：

[1] Columbia Univ, New York, NY, USA, Columbia Univ, New York, NY, USA

来源：

INFORMATION PROCESSING LETTERS | 1988年 / 28卷 / 01期

关键词：

DATA PROCESSING - Data Structures - MATHEMATICAL TECHNIQUES - Graph Theory;

D O I：

10.1016/0020-0190(88)90136-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The author considers directed acyclic graphs (DAGs), and shows how to return an arbitrarily chosen path between couples of nodes (if it exists) during the deletion of edges in an efficient manner. In particular, he proves that given a DAG with m edges and n nodes, there exists a data structure supporting each searchpath operation in O(l) time, where l is the length of the achieved path, and any number of delete operations in O(mn) worst-case time. Its space complexity is O(n**2). 18 Refs.

引用

页码：5 / 11

页数：7

共 17 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

AUSIELLO G, 1987, 13TH IFIP C SYST MOD

[3]

EVEN S, 1981, J ACM, V28, P1, DOI 10.1145/322234.322235

[4] DATA-STRUCTURES FOR ONLINE UPDATING OF MINIMUM SPANNING-TREES, WITH APPLICATIONS [J].