The arborescence-realization problem

The arborescence-realization problem

0.00 Avg rating0 Votes
Article ID: iaor19971018
Country: Netherlands
Volume: 59
Issue: 3
Start Page Number: 367
End Page Number: 383
Publication Date: May 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: combinatorial analysis
Abstract:

A {0,1}-matrix M is arborescence graphic if there exists an arborescence T such that the arcs of T are indexed on the rows of M and the columns of M are the incidence vectors of the arc sets of dipaths of T. If such a T exists, then T is an arborescence realization for M. This paper presents an almost-linear-time algorithm to determine whether a given {0,1}-matrix is arborescence graphic and, if so, to construct an arborescence realization. The algorithm is then applied to recognize a subclass of the extended-Horn satisfiability problems introduced by Chandru and Hooker.

Reviews

Required fields are marked *. Your email address will not be published.