OPUS


Volltext-Downloads (blau) und Frontdoor-Views (grau)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 85 of 1261
Back to Result List

Path Decomposition of Graphs and Algorithmic Applications

  • Path decomposition of a graph has received an important amount of interest over the past decades because of its applications in algorithmic graph theory and in real life problems. For the computation of a path decomposition of small width, we use different heuritics approaches. One of the most useful method is by Bodlaender and Kloks. In this thesis, we focus on the computation, applications, transformation and approximation of a path decomposition of small width. It is easy to convert a path decomposition in to nice path decomposition with same width, which is more convinent to use to find the graph parameters like independent sets, chromatic polynomials etc. Inspired by [28], we find an algorithm to compute the chromatic polynomial of a graph via nice path decomposition with small width.

Download full text files

  • master_thesis.pdf
    eng

Export metadata

Additional Services

Search Google Scholar

Statistics

frontdoor_oas
Metadaten
Author:Indra Prasad Dhakal
Advisor:Peter Tittmann, Klaus Dohmen
Document Type:Master's Thesis
Language:English
Year of Completion:2018
Granting Institution:Hochschule Mittweida
Release Date:2019/12/10
GND Keyword:Graph; Algorithmus
Institutes:Angewandte Computer‐ und Bio­wissen­schaften
DDC classes:511 Allgemeine mathematische Prinzipien
Open Access:Innerhalb der Hochschule
Licence (German):License LogoUrheberrechtlich geschützt