### Abstract

Original language | English |
---|---|

Title of host publication | Algorithms and Computation |

Subtitle of host publication | 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings |

Editors | Leizhen Cai, Sui-Wing Cheng, Tak-Wah Lam |

Place of Publication | Germany |

Publisher | Springer |

Pages | 372-382 |

Number of pages | 11 |

ISBN (Print) | 978-3-642-45029-7 |

DOIs | |

Publication status | Published - 2013 |

Event | 24th International Symposium, ISAAC 2013 - Hong Kong, China Duration: 16 Dec 2013 → 18 Dec 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 8283 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 24th International Symposium, ISAAC 2013 |
---|---|

Period | 16/12/13 → 18/12/13 |

### Fingerprint

### Cite this

*Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings*(pp. 372-382). (Lecture Notes in Computer Science ; Vol. 8283). Germany: Springer. https://doi.org/10.1007/978-3-642-45030-3_35

}

*Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings.*Lecture Notes in Computer Science , vol. 8283, Springer, Germany, pp. 372-382, 24th International Symposium, ISAAC 2013, 16/12/13. https://doi.org/10.1007/978-3-642-45030-3_35

**Myhill-Nerode Methods for Hypergraphs.** / Van Bevern, Rene; Fellows, Michael; Gaspers, Serge; Rosamond, Frances.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › peer-review

TY - GEN

T1 - Myhill-Nerode Methods for Hypergraphs

AU - Van Bevern, Rene

AU - Fellows, Michael

AU - Gaspers, Serge

AU - Rosamond, Frances

PY - 2013

Y1 - 2013

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.

KW - Cutwidths

KW - Finite tree automaton

KW - Formal language theory

KW - Hyper graph

KW - Incidence graphs

KW - Linear-time

KW - Parameterized complexity

KW - Tree-width

KW - Algorithms

KW - Automata theory

KW - Formal languages

KW - Graph theory

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

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

M3 - Conference Paper published in Proceedings

SN - 978-3-642-45029-7

T3 - Lecture Notes in Computer Science

SP - 372

EP - 382

BT - Algorithms and Computation

A2 - Cai, Leizhen

A2 - Cheng, Sui-Wing

A2 - Lam, Tak-Wah

PB - Springer

CY - Germany

ER -