Search for dissertations about: "Bipartite graph"

Showing result 1 - 5 of 11 swedish dissertations containing the words Bipartite graph.

  2. 1. 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

  4. 2. 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

  5. 3. 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

  6. 4. On Approximating Asymmetric TSP and Related Problems

    Author : Anna Palbom; Mikael Goldmann; Lars Engebretsen; Peter Jonsson; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Komplexity theory; algorithms; approxiamtion; Computer science; Datalogi;

    Abstract : In this thesis we study problems related to approximation of asymmetric TSP. First we give worst case examples for the famous algorithm due to Frieze, Gabiati and Maffioli for asymmetric TSP with triangle inequality. Some steps in the algorithm consist of arbitrary choices. To prove lower bounds, these choices need to be specified. READ MORE

  7. 5. On Long Proofs of Simple Truths

    Author : Kilian Risse; Per Austrin; Johan Håstad; Jakob Nordström; Benjamin Rossman; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computational Complexity; Lower Bounds; Proof Complexity; Datalogi; Computer Science;

    Abstract : Propositional proof complexity is the study of certificates of infeasibility. In this thesis we consider several proof systems with limited deductive ability and unconditionally show that they require long refutations of the feasibility of certain Boolean formulas. READ MORE