Sökning: "combinatorial algorithms"

Visar resultat 1 - 5 av 57 avhandlingar innehållade orden combinatorial algorithms.

1. 1. On Some Combinatorial Optimization Problems : Algorithms and Complexity

   Författare :Hannes Uppman; Peter Jonsson; Christer Bäckström; Ulf Nilsson; Stanislav Živný; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

   Sammanfattning : This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). LÄS MER

3. 2. Certifying Correctness for Combinatorial Algorithms : by Using Pseudo-Boolean Reasoning

   Författare :Stephan Gocht; Parallella System; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; certifying algorithms; 0-1 linear inequalities; combinatorial algorithms; proof logging;

   Sammanfattning : Over the last decades, dramatic improvements in combinatorialoptimisation algorithms have significantly impacted artificialintelligence, operations research, and other areas. These advances,however, are achieved through highly sophisticated algorithms that aredifficult to verify and prone to implementation errors that can causeincorrect results. LÄS MER

4. 3. Studies in Efficient Discrete Algorithms

   Författare :DZMITRY SLEDNEU; Matematik (naturvetenskapliga fakulteten); []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Algorithms; Approximation algorithms; Graphs;

   Sammanfattning : This thesis consists of five papers within the design and analysis of efficient algorithms.In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs. LÄS MER

5. 4. New Results on Combinatorial Algorithms

   Författare :Anders Dessmark; Data Vetenskap; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Sorting; Subgraph isomorphism; Partial k-trees; computer technology; Time complexity; Parallel computation; Data- och systemvetenskap; Convex layers; Systems engineering; Broadcasting;

   Sammanfattning : In this thesis improved upper bounds for several important combinatorial problems are provided. Below is a list of the main results showed in the thesis. The problem of determining whether a k-connected partial k-tree is isomorphic to subgraph of another partial k-tree is shown to be solvable in time O(nk+2). LÄS MER

7. 5. Network capacity sharing with QoS as a financial derivative pricing problem : algorithms and network design

   Författare :Lars Rasmusson; KTH; []
   Nyckelord :Computer network architecture; bandwidth trading; inter-domain Quality-of-Service; pricing; combinatorial allocation; financial derivative pricing; stochastic modeling;

   Sammanfattning : A design of anautomatic network capacity markets, oftenreferred to as a bandwidth market, is presented. Three topicsare investigated. First, a network model is proposed. Theproposed model is based upon a trisection of the participantroles into network users, network owners, and market middlemen. LÄS MER