On Total Unimodularity of Edge‐Edge Adjacency Matrices

On Total Unimodularity of Edge‐Edge Adjacency Matrices

0.00 Avg rating0 Votes
Article ID: iaor20134083
Volume: 67
Issue: 2
Start Page Number: 277
End Page Number: 292
Publication Date: Oct 2013
Journal: Algorithmica
Authors: , ,
Keywords: matrices, programming: integer
Abstract:

We consider total unimodularity for edge–edge adjacency matrices that represent adjacency relations between pairs of edges in a graph. These matrices appear in integer programming formulations of the minimum maximal matching problem, the edge dominating set problem, and so on. We investigate the problem of characterizing graphs that have totally unimodular edge–edge adjacency matrices, and give a necessary and sufficient condition for characterization. This condition is the first characterization for total unimodularity of edge–edge adjacency matrices.

Reviews

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