Myhill-Nerode methods for hypergraphs

René Van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

4 Цитирования (Scopus)

Аннотация

We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Страницы372-382
Число страниц11
DOI
СостояниеОпубликовано - 1 дек 2013
Опубликовано для внешнего пользованияДа
Событие24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, Китай
Продолжительность: 16 дек 201318 дек 2013

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том8283 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция24th International Symposium on Algorithms and Computation, ISAAC 2013
СтранаКитай
ГородHong Kong
Период16.12.201318.12.2013

Fingerprint Подробные сведения о темах исследования «Myhill-Nerode methods for hypergraphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Fellows, M. R., Gaspers, S., & Rosamond, F. A. (2013). Myhill-Nerode methods for hypergraphs. В Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings (стр. 372-382). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8283 LNCS). https://doi.org/10.1007/978-3-642-45030-3_35