A slice theoretic approach for embedding problems on digraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00461744" target="_blank" >RIV/67985840:_____/16:00461744 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-53174-7_26" target="_blank" >http://dx.doi.org/10.1007/978-3-662-53174-7_26</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-53174-7_26" target="_blank" >10.1007/978-3-662-53174-7_26</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A slice theoretic approach for embedding problems on digraphs

Popis výsledku v původním jazyce

We say that a digraph H can be covered by k paths if there exist k directed paths ... such that ... In this work we devise parameterized algorithms for embedding problems on digraphs in the setting in which the host digraph G has directed pathwidth w and the pattern digraph H can be covered by k paths. More precisely, we show that the subgraph isomorphism, subgraph homeomorphism, and two other related embedding problems can each be solved in time ... We note in particular that for constant values of w and k, our algorithm runs in polynomial time with respect to the size of the pattern digraph H. Therefore for the classes of digraphs considered in this work our results yield an exponential speedup with respect to the best general algorithm for the subgraph isomorphism problem which runs in time ...

Název v anglickém jazyce

A slice theoretic approach for embedding problems on digraphs

Popis výsledku anglicky

We say that a digraph H can be covered by k paths if there exist k directed paths ... such that ... In this work we devise parameterized algorithms for embedding problems on digraphs in the setting in which the host digraph G has directed pathwidth w and the pattern digraph H can be covered by k paths. More precisely, we show that the subgraph isomorphism, subgraph homeomorphism, and two other related embedding problems can each be solved in time ... We note in particular that for constant values of w and k, our algorithm runs in polynomial time with respect to the size of the pattern digraph H. Therefore for the classes of digraphs considered in this work our results yield an exponential speedup with respect to the best general algorithm for the subgraph isomorphism problem which runs in time ...

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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ů

Název statě ve sborníku

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-662-53173-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

360-372

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Garching

Datum konání akce

17. 6. 2015

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

WRD - Celosvětová akce

Kód UT WoS článku

000389704200026