Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

SAT-Encodings for Treecut Width and Treedepth

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113720" target="_blank" >RIV/00216224:14330/19:00113720 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://epubs.siam.org/doi/10.1137/1.9781611975499.10" target="_blank" >https://epubs.siam.org/doi/10.1137/1.9781611975499.10</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1137/1.9781611975499.10" target="_blank" >10.1137/1.9781611975499.10</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    SAT-Encodings for Treecut Width and Treedepth

  • Popis výsledku v původním jazyce

    The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided; the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters tree-cut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms.

  • Název v anglickém jazyce

    SAT-Encodings for Treecut Width and Treedepth

  • Popis výsledku anglicky

    The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided; the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters tree-cut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

  • OECD FORD obor

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

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2019

  • Kód důvěrnosti údajů

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

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    ALENEX 2019

  • ISBN

    9781611975499

  • ISSN

    2164-0300

  • e-ISSN

  • Počet stran výsledku

    13

  • Strana od-do

    117-129

  • Název nakladatele

    SIAM

  • Místo vydání

    USA

  • Místo konání akce

    USA

  • Datum konání akce

    1. 1. 2019

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku