Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"cographic"”.
-
Polytopes of Cographic Unimodular Systems and Valuated Delta-Matroids
… to address this in the more unknown case of the cographic matroids, duals of the graphic matroid. To the associated polytopes, will introduce a characterization for both the normal fans and the support functions. Additionally, with valuated delta matroids, we introduce an object that …
-
Single Commodity Flow Algorithms for Lifts of Graphic and Cographic Matroids
… We show that if M is a lift of a graphic or a cographic matroid, then in polynomial time we can either solve the single commodity flow problem for M or find an obstruction for which the Max-Flow Min-Cut relation does not hold. The key tool is an algorithmic version of Lehman's Theorem for the …
-
Recognizing Even-Cycle and Even-Cut Matroids
… that generalize respectively graphic and cographic matroids. We give algorithms to check membership for these classes of matroids. We assume that the matroids are 3-connected and are given by their (0,1)-matrix representations. We first give an algorithm to check membership for p-cographic …
-
Structural properties of signed - graphic matroids
… matroids is decomposed and the classes of cographic signed-graphic matroids and binary signed-graphic matroids are characterized. More precisely, a characterization of the class of cographic signed-graphic matroids which is based on properties of cocircuits is provided. Furthermore, we …
-
Constructing stability conditions on nodal curves from subdivisions of Lawrence polytopes
… subdivisions of the Lawrence polytope of the cographic matroid $\M^\ast(G)$ using the theory of single-element extensions of oriented matroids. We also discuss connections to chip-firing on graphs through the theory of generalized break divisors.
-
Thickened Surfaces, Checkerboard Surfaces, and Quantum Link Invariants
… we develop a theory of Goeritz matrices for cographic matroids, which extends the bracket polynomial to any symmetric integer matrix. We place this work in the context of links in thickened surfaces.
-
On Excluded Minors for Even Cut Matroids
… This is in contrast to, for instance graphic (or cographic) matroids, where all graphs corresponding to a particular graphic matroid are essentially equivalent. To tackle the multiple non equivalent representations of even cut matroids we use the concept of Stabilizer first introduced by Wittle. …
-
Even Cycle and Even Cut Matroids
… They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid …
-
Price-setting Problems and Matroid Bayesian Online Selection
… hardness results for both transversal and cographic matroids. We then turn our attention to a related problem where the arrival order of items is unknown and uniformly random. In this setting, we show that there is a polynomial-time approximation scheme whenever the rank of the matroid is …
-
Regular Round Matroids
A matroid M is a finite set E, called the ground set of M, together with a notion of what it means for subsets of E to be independent. Some matroids, called regular matroids, have the property that all elements in their ground set can be represented by vectors over any field. A matroid is called …