All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Structural graph theory and parameterized complexity

Project goals

Many real-world algorithmic problems turn out to be intractable in their full generality. Theory of parameterized complexity, however, provides a useful framework for a refined analysis of such hard problems, and for designing conceptually new algorithmsthat can solve hard problems for the real-world instances efficiently. In contrast to heuristics, this approach provides guarantied runtime bounds.Graphs are combinatorial structures suitable for modeling many discrete and optimization problems. Structural graph theory has already proved very useful in parameterized algorithmics. For instance, most of traditional hard problems are efficiently solvable on graphs of bounded tree-width. We plan to exploit other structural properties of graphs like branch-width, DAG-width, rank-width, or their topological properties. Our goal is to find new application areas of structural graph theory in parameterized algorithm design, by collaboration of our research groups from both areas.

Keywords

fixed parameter tractabilityexponential algorithmtree-widthgraph minortopological graph

Public support

  • Provider

    Czech Science Foundation

  • Programme

    International projects

  • Call for proposals

    Mezinárodní projekty 3 (SGA02009GA1GC)

  • Main participants

  • Contest type

    VS - Public tender

  • Contract ID

    201/09/J021

Alternative language

  • Project name in Czech

    Strukturální teorie grafů a parametrizovaná složitost

  • Annotation in Czech

    Mnoho algoritmických problémů z reálného světa se ukazují jako nezvladatelné v plné obecnosti. Teorie parametrizované složitosti nám však dává užitečný rámec nástrojů pro jemnější analýzu obtížnosti těchto těžkých problémů a pro návrh koncepčně nových algoritmů, které dokáží řešit reálné instance těžkých problémů efektivněji. Na rozdíl od heuristických přístupů tak získáme i garantované ohraničení času. Grafy jako kombinatorické struktury jsou vhodné pro modelování diskrétních a optimalizačních problémů. Přitom strukturální teorie grafů se ukazuje jako velmi užitečná v parametrizovaných algoritmech. Například většina tradičně těžkých problémů je rychle řešitelná na grafech omezené stromové šířky.Naším plánem je využít i další strukturální vlastnosti grafů jako větvená šířka, DAG šířka, ranková šířka, či jejich topologické vlastnosti. Cílem je nalézt nové oblasti aplikací strukturální teorie grafů v navrhování parametrizovaných algoritmů, čehož bude dosaženo spoluprácí našich výzkumných

Scientific branches

  • R&D category

    ZV - Basic research

  • CEP classification - main branch

    IN - Informatics

  • CEP - secondary branch

    BA - General mathematics

  • CEP - another secondary branch

  • 10101 - Pure mathematics
    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Completed project evaluation

  • Provider evaluation

    V - Vynikající výsledky projektu (s mezinárodním významem atd.)

  • Project results evaluation

    First we gave a thorough overview of parameterized complexity of known problems on directed graphs with respect to known directed ?width? measures. Moreover, we showed that most of these problems remain NP-complete even for very restricted classes of directed graphs (using two new measures DAG-depth and K-width). Some of the complexity bounds were taken from literature, however the rest was prove

Solution timeline

  • Realization period - beginning

    Jan 1, 2009

  • Realization period - end

    Dec 31, 2010

  • Project status

    U - Finished project

  • Latest support payment

    Apr 16, 2010

Data delivery to CEP

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

  • Data delivery code

    CEP11-GA0-GC-U/03:3

  • Data delivery date

    Feb 9, 2015

Finance

  • Total approved costs

    1,014 thou. CZK

  • Public financial support

    1,014 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK

Recognised costs

1 014 CZK thou.

Public support

1 014 CZK thou.

0%


Provider

Czech Science Foundation

CEP

IN - Informatics

Solution period

01. 01. 2009 - 31. 12. 2010