Sökning: "shortest cycle"

Visar resultat 1 - 5 av 12 avhandlingar innehållade orden shortest cycle.

1. 1. Exact and approximation algorithms for graph problems with some biological applications

   Författare :Eva-Marta Lundell; Data Vetenskap; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Graph algorithms; computational biology; approximation algorithms; computational complexity; evolutionary trees; maximum agreement subtree; graph embedding; shortest cycle; clique partitioning;

   Sammanfattning : In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them. In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions. LÄS MER

3. 2. Shortest Path Routing Modelling, Infeasibility and Polyhedra

   Författare :Mikael Call; Kaj Holmberg; Bernard Fortz; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

   Sammanfattning : The Internet is constantly growing but the available resources, i.e. bandwidth, are limited. Using bandwidth efficiently to provide high quality of service to users is referred to as traffic engineering. LÄS MER

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

   Författare :Jan van den Brand; Danupon Na Nongkai; Santosh Vempala; KTH; []
   Nyckelord :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;

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

5. 4. Logistic Time Requirements in Fast Sea Transportation Systems

   Författare :Thore E.W. Hagman; Chalmers tekniska högskola; []
   Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; cycle time; high speed; terminal time; performance; sailing time; total time; fuel consumption; logistic time requirement; power demand;

   Sammanfattning : The dissertation deals with logistic time requirements in fast sea transportation systems and the benefit of the application of the total time definition. The transportation engineering approach, to create new transport systems with high effectiveness, high service levels and also with high resource utilisation, has to some extent gained acceptance in the transportation industry, but it has not been fully realised that the transport system and the traffic system are not identical and that by focusing on high performance of the traffic system no guarantee is given that the transport system will become effective. LÄS MER

7. 5. Optimization Models and Methods for Telecommunication Networks using OSPF

   Författare :Peter Broström; Michal Pióro; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Telecommunication; OSPF; LP-duality; Polynomial methods; MATHEMATICS; MATEMATIK;

   Sammanfattning : The routing in OSPF Telecommunication networks is determined by computing shortest paths with respect to link weights set by the network operator. All shortest paths to a destination are used by the routers when traffic is routed, and the routers split the traffic evenly when alternative shortest paths exist. LÄS MER