Sökning: "Directed graph"

Visar resultat 11 - 15 av 42 avhandlingar innehållade orden Directed graph.

  1. 11. Approximating Longest Path

    Författare :Andreas Björklund; Institutionen för datavetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : We investigate the computational hardness of approximating the longest path and the longest cycle in undirected and directed graphs on n vertices. We show that * in any expander graph, we can find (n) long paths in polynomial time. LÄS MER

  3. 12. On a class of commutative algebras associated to graphs

    Författare :Gleb Nenashev; Boris Shapiro; Volkmar Welker; Stockholms universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : In 2004 Alexander Postnikov and Boris Shapiro introduced a class of commutative algebras for non-directed graphs. There are two main types of such algebras, algebras of the first type count spanning trees and algebras  of the second type count spanning forests. LÄS MER

  4. 13. Resource-Constrained Multi-Agent Control Systems: Dynamic Event-triggering, Input Saturation, and Connectivity Preservation

    Författare :Xinlei Yi; Karl H. Johansson; Lihua Xie; KTH; []
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Consensus; Connectivity; Dynamic event-triggered control; Formation control; Input saturation; Multi-agent systems; Self-triggered control; Electrical Engineering; Elektro- och systemteknik;

    Sammanfattning : 978-91-7729-579-2A multi-agent system consists of multiple agents cooperating to achieve a common objective through local interactions. An important problem is how to reduce the amount of information exchanged, since agents in practice only have limited energy and communication resources. LÄS MER

  5. 14. Dynamic Optimization of Transportation Networks with Delays

    Författare :Martin Heyden; Institutionen för reglerteknik; []
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY;

    Sammanfattning : The topic of this thesis is the optimal control of transportation networks. The problem studied is a dynamical extension of a classical problem in economics, in which the objective is to distribute goods to maximize welfare, whilst satisfying constraints on production and consumption. LÄS MER

  7. 15. On Approximating Asymmetric TSP and Related Problems

    Författare :Anna Palbom; Mikael Goldmann; Lars Engebretsen; Peter Jonsson; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Komplexity theory; algorithms; approxiamtion; Computer science; Datalogi;

    Sammanfattning : 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. LÄS MER