Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00144
Finding a Nonempty Algebraic Subset of an Edge Set in Linear Time
Vol. 11, no. 1, pp. 239257, 2007. Regular paper.
Abstract A set of edges of a hypergraph H is an algebraic set if
its characteristic vector can be expressed as a linear combination of
rows of the (nodeedge) incidence matrix of H. Recently it was proven
that deciding whether or not a given edgeset of H contains
a nonempty algebraic set is an NPcomplete problem. In this
paper we give a linear time algorithm to decide if a given edgeset
contains a nonempty algebraic set when the hypergraph is a graph.
