Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00144 Finding a Nonempty Algebraic Subset of an Edge Set in Linear Time Mauro Mezzini Vol. 11, no. 1, pp. 239-257, 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 (node-edge) incidence matrix of H. Recently it was proven that deciding whether or not a given edge-set of H contains a non-empty algebraic set is an NP-complete problem. In this paper we give a linear time algorithm to decide if a given edge-set contains a non-empty algebraic set when the hypergraph is a graph.
|
Submitted: November 2005. Revised: January 2007. Communicated by Larse Arge |
Journal of Graph Algorithms and Applications |