Total unimodularity and the Euler-subgraph problem |
| |
| Affiliation: | 1. Corvinus University of Budapest, Department of Operations Research and Actuarial Sciences, H-1093 Budapest Fővám tér 8., Hungary;2. ‘Momentum’ Game Theory Research Group, Centre for Economic and Regional Studies, Hungarian Academy of Sciences, H-1112 Budapest Budaörsi út 45., Hungary;1. School of Operations Research and Information Engineering, Department of Computer Science, Cornell University, Ithaca NY, USA;2. Optimisation Combinatoire (G-SCOP), CNRS, Univ. Grenoble Alpes, Grenoble, France;3. Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany;4. Department of Mathematics, College of William & Mary, Williamsburg VA, USA;1. Delft Institute of Applied Mathematics, TU Delft, The Netherlands;2. Centrum Wiskunde en Informatica, Amsterdam, The Netherlands;3. H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, NW, Atlanta, GA 30332-0205, United States |
| |
| Abstract: | We give a short treatment (including proofs) of all known characterizations by way of forbidden structures of totally unimodular matrices, i.e. matrices whose square minors have determinants of 0, +1, or −1 only. A generalization of a known topological characterization gives rise to a new combinatorial optimization problem which is introduced here and called the Euler-subgraph problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
