Standard

Myhill-Nerode methods for hypergraphs. / Van Bevern, René; Fellows, Michael R.; Gaspers, Serge и др.

Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. стр. 372-382 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8283 LNCS).

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

Harvard

Van Bevern, R, Fellows, MR, Gaspers, S & Rosamond, FA 2013, Myhill-Nerode methods for hypergraphs. в Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 8283 LNCS, стр. 372-382, 24th International Symposium on Algorithms and Computation, ISAAC 2013, Hong Kong, Китай, 16.12.2013. https://doi.org/10.1007/978-3-642-45030-3_35

APA

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

Vancouver

Van Bevern R, Fellows MR, Gaspers S, Rosamond FA. Myhill-Nerode methods for hypergraphs. в Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. стр. 372-382. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-45030-3_35

Author

Van Bevern, René ; Fellows, Michael R. ; Gaspers, Serge и др. / Myhill-Nerode methods for hypergraphs. Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. стр. 372-382 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{fd7871ce17bd404dbf26367e2dad6769,
title = "Myhill-Nerode methods for hypergraphs",
abstract = "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.",
author = "{Van Bevern}, Ren{\'e} and Fellows, {Michael R.} and Serge Gaspers and Rosamond, {Frances A.}",
year = "2013",
month = dec,
day = "1",
doi = "10.1007/978-3-642-45030-3_35",
language = "English",
isbn = "9783642450297",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "372--382",
booktitle = "Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings",
note = "24th International Symposium on Algorithms and Computation, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

}

RIS

TY - GEN

T1 - Myhill-Nerode methods for hypergraphs

AU - Van Bevern, René

AU - Fellows, Michael R.

AU - Gaspers, Serge

AU - Rosamond, Frances A.

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893390048&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45030-3_35

DO - 10.1007/978-3-642-45030-3_35

M3 - Conference contribution

AN - SCOPUS:84893390048

SN - 9783642450297

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 372

EP - 382

BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings

T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013

Y2 - 16 December 2013 through 18 December 2013

ER -

ID: 22340716