FO model checking; parameterized complexity; interval graph; clique-width

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F13%3A43919150" target="_blank" >RIV/49777513:23520/13:43919150 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_24" target="_blank" >http://dx.doi.org/10.1007/978-3-642-39212-2_24</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-39212-2_24" target="_blank" >10.1007/978-3-642-39212-2_24</a>

Jazyk výsledku
angličtina
Název v původním jazyce
FO model checking; parameterized complexity; interval graph; clique-width
Popis výsledku v původním jazyce
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that this problem can be solved in time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in some open subset, e.g., in the set (1,1 +?).
Název v anglickém jazyce
FO model checking; parameterized complexity; interval graph; clique-width
Popis výsledku anglicky
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that this problem can be solved in time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in some open subset, e.g., in the set (1,1 +?).

Projekt
<a href="/cs/project/GAP202%2F11%2F0196" target="_blank" >GAP202/11/0196: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2013
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
Proceedings of 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
ISBN
978-3-642-39211-5
ISSN
—
e-ISSN
—
Počet stran výsledku
13
Strana od-do
250-262
Název nakladatele
Springer
Místo vydání
Heidelberg
Místo konání akce
Riga, Litva
Datum konání akce
8. 7. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)