Graphs and matroids
Abstract
Matroids are combinatorial abstractions of geometry that arise in many settings including optimization, theoretical computer science"", and physics. Graphic matroids form a particularly nice class in that there are many problems whichcan be efficiently solved on th""e class that are intractable for matroids in general; moreover, the class is well understood from the point of view characterization""s and recognition algorithms. This proposal concerns generalizations of graphic matroids; in particular, frame matroids, lifted-grap""hic matroids, andquasi-graphic matroids. These classes have similar nice properties to the graphic matroids. However, lifted-graphi"c matroids and frame matroids do not seem to admit nice characterizations or efficient recognition algorithms. The quasigraphic matroids were recently introduced as a common generalization of the frame matroids and the lifted-graphic matroids. The goal of the proposal is to develop characterizations and a recognition algorithm for this broader class.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 23, 2018
- Source ID
- N000141812076
Entities
People
- James Geelen
Organizations
- Office of Naval Research
- United States Navy
- University of Waterloo