Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Myhill-Nerode methods for hypergraphs

Van, Bevern, Fellows, Michael R., Gaspers, Serge and Rosamond, Frances A. (2013). Myhill-Nerode methods for hypergraphs. In: 24th International Symposium on Algorithms and Computation (ISAAC 2013), University of Hong Kong, Hong Kong, China, 16-18 December 2013.

Document type: Conference Paper

IRMA ID 82794376xPUB261
Author Van, Bevern
Fellows, Michael R.
Gaspers, Serge
Rosamond, Frances A.
Title Myhill-Nerode methods for hypergraphs
Conference Name 24th International Symposium on Algorithms and Computation (ISAAC 2013)
Conference Location University of Hong Kong, Hong Kong, China
Conference Dates 16-18 December 2013
Conference Publication Title Lecture Notes in Computer Science 8283: Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings
Place of Publication Germany
Publisher Springer
Publication Year 2013
Volume Number 8283 LNCS
ISBN 978-3-642-45029-7   (check CDU catalogue  open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue  open catalogue search in new window)
Start Page 372
End Page 382
Total Pages 11
HERDC Category E1 - Conference Publication (DIISR)
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.
Additional Notes PDF for ERA has 34 pages
Description for Link Link to conference homepage
Link to publisher's homepage
URL http://www.cs.hku.hk/isaac2013/index.html
http://link.springer.com/chapter/10.1007%2F978-3-642-45030-3_35#
 
Versions
Version Filter Type
Access Statistics: 35 Abstract Views, 9 File Downloads  -  Detailed Statistics
Created: Thu, 07 Aug 2014, 16:39:58 CST