On totally unimodularity of edge-edge adjacency matrices

Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider totally unimodularity for edge-edge adjacency matrices which represent a relationship between two edges in a graph. The matrices appear in integer programming formulations for the minimum maximal matching problem and the edge dominating set problem. We consider a problem of characterizing graphs having totally unimodular matrices as their edge-edge adjacency matrices, and give a necessary and sufficient condition for the characterization. The condition is the first characterization for edge-edge adjacency matrices.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
Number of pages12
Publication statusPublished - 2011
Externally publishedYes
Event17th Annual International Computing and Combinatorics Conference, COCOON 2011 - Dallas, TX, United States
Duration: Aug 14 2011Aug 16 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6842 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other17th Annual International Computing and Combinatorics Conference, COCOON 2011
Country/TerritoryUnited States
CityDallas, TX

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On totally unimodularity of edge-edge adjacency matrices'. Together they form a unique fingerprint.

Cite this