Myhill-Nerode Methods for Hypergraphs
From MaRDI portal
Publication:2872101
DOI10.1007/978-3-642-45030-3_35zbMath1329.68129arXiv1211.1299OpenAlexW2616733098WikidataQ57359615 ScholiaQ57359615MaRDI QIDQ2872101
Serge Gaspers, René van Bevern, Michael R. Fellows, Frances A. Rosamond, Rodney G. Downey
Publication date: 14 January 2014
Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.1299
Hypergraphs (05C65) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Parameterized complexity of computing maximum minimal blocking and hitting sets, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Approximability and parameterized complexity of multicover by \(c\)-intervals, Myhill-Nerode Methods for Hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Constraint satisfaction with bounded treewidth revisited
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Derivation of algorithms for cutwidth and related graph layout parameters
- Regularity and locality in \(k\)-terminal graphs
- On search, decision, and the efficiency of polynomial-time algorithms
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Conjunctive-query containment and constraint satisfaction
- ``Global graph problems tend to be intractable
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Parametrized complexity theory.
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Myhill-Nerode Methods for Hypergraphs
- New Races in Parameterized Algorithmics
- Approximating fractional hypertree width
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Linear Automaton Transformations
- Generalized hypertree decompositions: NP-hardness and tractable variants
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Complexity Results for Bandwidth Minimization
- Equivalent definitions of recognizability for sets of graphs of bounded tree-width
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Linear Layouts in Submodular Systems
- Two strikes against perfect phylogeny
- Cutwidth I: A linear time fixed parameter algorithm
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
- Graph-Theoretic Concepts in Computer Science
