Representation of bicircular matroids

Representation of bicircular matroids

0.00 Avg rating0 Votes
Article ID: iaor1992262
Country: Netherlands
Volume: 32
Issue: 3
Start Page Number: 223
End Page Number: 240
Publication Date: Aug 1991
Journal: Discrete Applied Mathematics
Authors: , ,
Abstract:

A bicircular matroid is a matroid defined on the edge set of a graph. Two different graphs can have the same bicircular matroid. The first result of this paper is a characterization of the collection of graphs having the same bicircular matroid as a given arbitrary graph. A bicircular matroid can be represented by a matrix over the real numbers that has at most two nonzeros per column. Such a matrix can be viewed as an incidence matrix of a graph. The second result of this paper is that given almost any (in a sense to be made precise) collection of graphs G1,...,Gt having the same bicircular matroid M, there exist row-equivalent matrices N1,...,Nt each representing M, such that Ni is an incidence matrix of Gi for 1•i•t. These results form the basis for an algorithm (presented in a subsequent paper) that under certain conditions converts a given linear-programming problem to a generalized-network flow problem.

Reviews

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