Standard
Myhill-Nerode methods for hypergraphs. / Van Bevern, René; Fellows, Michael R.; Gaspers, Serge et al.
Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. p. 372-382 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Fellows, MR, Gaspers, S & Rosamond, FA 2013,
Myhill-Nerode methods for hypergraphs. in
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), vol. 8283 LNCS, pp. 372-382, 24th International Symposium on Algorithms and Computation, ISAAC 2013, Hong Kong, China,
16.12.2013.
https://doi.org/10.1007/978-3-642-45030-3_35
APA
Vancouver
Van Bevern R, Fellows MR, Gaspers S, Rosamond FA.
Myhill-Nerode methods for hypergraphs. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. p. 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 et al. /
Myhill-Nerode methods for hypergraphs. Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. pp. 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 -
