Algorithms for parsimonious complete sets in directed graphs

We are given: a directed graph G = ( V, E); for each vertex υ ϵ V, a collection P( υ) of sets of predecessors of υ; and a target vertex t. Define a subset C of vertices to be complete if for each υ ϵ C there is some set Q ϵ P( υ) such that Q ⊆ C. We say that C is complete for t if in addition t ϵ C....

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1996-09, Vol.59 (6), p.335-339
Main Authors: Melkman, Avraham A., Shimony, Solomon E.
Format: Article
Language:English
Subjects:
Abduction
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Complete sets
Computer science
control theory
systems
Exact sciences and technology
Graphs
Information processing
Information retrieval. Graph
Parsimonious
Proof graphs
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We are given: a directed graph G = ( V, E); for each vertex υ ϵ V, a collection P( υ) of sets of predecessors of υ; and a target vertex t. Define a subset C of vertices to be complete if for each υ ϵ C there is some set Q ϵ P( υ) such that Q ⊆ C. We say that C is complete for t if in addition t ϵ C. The problem is to find a parsimonious (minimal with respect to set-inclusion) set that is complete for t. This paper presents efficient algorithms for solving the problem, for general graphs and for acyclic ones. In the special case where G is acyclic, and has bounded in-degree, the algorithm presented has time complexity O(¦V¦).
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(96)00123-8