A slice theoretic approach for embedding problems on digraphs

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
A slice theoretic approach for embedding problems on digraphs
Original language description
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 ...
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)