Strong unimodularity for matrices and hypergraphs
type: Item
instance of: scholarly article
title: Strong unimodularity for matrices and hypergraphs
zbMATH Open document ID: 0647.05042
DOI: 10.1016/0166-218X(86)90044-2
author: Peter L. Hammer
author: Toshihide Ibaraki
author: Yves Crama
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: A 0-1 matrix A is called strongly unimodular if all the bases of (A,I) are triangular. We develop equivalent conditions for strong unimodularity, first in algebraic, then in graph theoretic terms. This provides a link with the theory of unimodular and balanced hypergraphs, and allows us to produce a polynomial-time recognition algorithm for strongly unimodular matrices. We consider next the constraint matrix of the problem obtained by linearizing a general, unconstrained optimization problem in 0-1 variables. Because that matrix has 0, 1 and -1 entries, we are led to introduce the concept of signed hypergraph in which every edge is affected of a positive or negative sign. Our results on strong unimodularity are extended to the class of signed hypergraphs.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 4055658
zbMATH Keywords: 0-1 matrix
zbMATH Keywords: strongly unimodular
zbMATH Keywords: signed hypergraph
MaRDI profile type: Publication
cites work: Hypergraphs with no special cycles
cites work: Balanced matrices
cites work: Q3941433
cites work: Q5538300
cites work: Unimodular functions
cites work: On the notion of balance of a signed graph
cites work: Q3737235
cites work: Q3236252
cites work: A Selection Problem of Shared Fixed Costs and Network Flows
cites work: Decomposition of regular matroids
description: scientific article; zbMATH DE number 4055658