Search for dissertations about: "BIPARTITE GRAPHS"

Showing result 1 - 5 of 11 swedish dissertations containing the words BIPARTITE GRAPHS.

  2. 1. Simplicial Complexes of Graphs

    Author : Jakob Jonsson; Anders Björner; John Shareshian; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Algebra and geometry; simplicial complex; monotone graph property; discrete Morse theory; simplicial homology; homotopy type; connectivity degree; Cohen-Macaulay complex; Euler characteristic; decision tree; Algebra och geometri; Algebra and geometry; Algebra och geometri;

    Abstract : Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. READ MORE

  4. 2. Quantum Graphs and Equi-transmitting Scattering Matrices

    Author : Wyclife Ogik Rao; Pavel Kurasov; Rikard Bogvad; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Quantum graphs; vertex scattering matrix; equi-transmitting matrices.; matematik; Mathematics;

    Abstract : The focus of this study is scattering matrices in the framework of quantum graphs,more precisely the matrices which describe equi-transmission. They are unitary andHermitian and are independent of the energies of the associated system. READ MORE

  5. 3. The k-assignment Polytope and the Space of Evolutionary Trees

    Author : Jonna Gill; Svante Linusson; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; k-assignment; polytope; Birkhoff polytope; bipartite graphs; MATHEMATICS; MATEMATIK;

    Abstract : This thesis consists of two papers.The first paper is a study of the structure of the k-assignment polytope, whose vertices are the m x n (0; 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. READ MORE

  6. 4. Dynamic Matrix Algorithms and Applications in Convex and Combinatorial Optimization

    Author : Jan van den Brand; Danupon Na Nongkai; Santosh Vempala; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Dynamic Algorithm; Data Structure; Optimization; Linear Program; Bipartite Matching; Shortest Path; Maximum Flow; Minimum Cost Flow; Diameter; Computer Science; Datalogi;

    Abstract : Dynamic algorithms are used to efficiently maintain solutions to problems where the input undergoes some changes.This thesis studies dynamic algorithms that maintain solutions to linear algebra problems and we explore their applications and implications for dynamic graphs and optimization problems. READ MORE

  7. 5. On random satisfiability and optimization problems

    Author : Joel Larsson; Klas Markström; Roland Häggkvist; Victor Falgas Ravry; Stefanie Gerke; Umeå universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Random graphs; k-SAT; satisfiability; coupon collector; random cover time; threshold phenomenon; concentration of measure; combinatorial probability; perfect matching; assignment problem; local graph limit; mean-field; Mathematics; matematik;

    Abstract : In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. READ MORE