A note on computing graph closures

This note shows that the k-closure of a graph can be computed in time proportional to the size of the output, improving on previous O( n 3) algorithms.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2004-02, Vol.276 (1), p.327-329
Main Author: Spinrad, Jeremy P.
Format: Article
Language:English
Subjects:
Algorithm
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph closure
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This note shows that the k-closure of a graph can be computed in time proportional to the size of the output, improving on previous O( n 3) algorithms.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(03)00316-9