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 >= 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 >= 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
—