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”

MSOL restricted contractibility to planar graphs

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368365" target="_blank" >RIV/00216208:11320/17:10368365 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://dx.doi.org/10.1016/j.tcs.2017.02.030" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2017.02.030</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.tcs.2017.02.030" target="_blank" >10.1016/j.tcs.2017.02.030</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    MSOL restricted contractibility to planar graphs

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

    We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We work with a more general problem called P-RESTRICTEDCONTRACT in which S, in addition, is required to satisfy a fixed MSOL formula P(S, G). We give an FPT algorithm in time O(n(2) f (k)) which solves P-RESTRICTEDCONTRACT, where n is number of vertices of the graph and P(S, G) is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion-minimal solution S). As a specific example, we can solve the l-subgraph contractibility problem in which the edges of the set S are required to form disjoint connected subgraphs of size at most l. This problem can be solved in time O(n(2) (k, l)) using the general algorithm. We also show that for l &gt;= 2 the problem is NP-complete.

  • Název v anglickém jazyce

    MSOL restricted contractibility to planar graphs

  • Popis výsledku anglicky

    We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We work with a more general problem called P-RESTRICTEDCONTRACT in which S, in addition, is required to satisfy a fixed MSOL formula P(S, G). We give an FPT algorithm in time O(n(2) f (k)) which solves P-RESTRICTEDCONTRACT, where n is number of vertices of the graph and P(S, G) is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion-minimal solution S). As a specific example, we can solve the l-subgraph contractibility problem in which the edges of the set S are required to form disjoint connected subgraphs of size at most l. This problem can be solved in time O(n(2) (k, l)) using the general algorithm. We also show that for l &gt;= 2 the problem is NP-complete.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • 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

    <a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Ostatní

  • Rok uplatnění

    2017

  • 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 periodika

    Theoretical Computer Science

  • ISSN

    0304-3975

  • e-ISSN

  • Svazek periodika

    676

  • Číslo periodika v rámci svazku

    Květen

  • Stát vydavatele periodika

    NL - Nizozemsko

  • Počet stran výsledku

    14

  • Strana od-do

    1-14

  • Kód UT WoS článku

    000401399800001

  • EID výsledku v databázi Scopus