Characterization and complexity of uniformly nonprimitive labeled 2-structures
From MaRDI portal
Publication:672749
DOI10.1016/0304-3975(94)00272-XzbMath0873.68161MaRDI QIDQ672749
Grzegorz Rozenberg, Andrzej Proskurowski, Tero J.Harju, Joost Engelfriet
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
LOGCF algorithmMSO (monadic second-order) definable propertyparallel complexity of the decomposition of 2-structures
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Monadic second-order definable text languages ⋮ Complete edge-colored permutation graphs ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Automata-based Representations for Infinite Graphs ⋮ Theory of 2-structures ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ From modular decomposition trees to rooted median graphs ⋮ Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees ⋮ Permutations, parenthesis words, and Schröder numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Forbidden minors characterization of partial 3-trees
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
- Primitivity is hereditary for 2-structures
- The method of forced enumeration for nondeterministic automata
- Tree-size bounded alternation
- On uniform circuit complexity
- Complement reducible graphs
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Angular 2-structures
- Either tournaments or algebras?
- Incremental construction of 2-structures
- Primitive 2-structures with the \((n-2)\)-property
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- On certain polytopes associated with graphs
- Graphs indecomposable with respect to the X-join
- The complexity of graph languages generated by hyperedge replacement
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Tree acceptors and some of their applications
- Embedding tournaments in simple tournaments
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Steiner trees, partial 2–trees, and minimum IFI networks
- Easy problems for tree-decomposable graphs
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Characterization and Recognition of Partial 3-Trees
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Nondeterministic Space is Closed under Complementation
- Incremental modular decomposition
- Alternation
- The Recognition of Series Parallel Digraphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- On the Tape Complexity of Deterministic Context-Free Languages
- Transitiv orientierbare Graphen
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Modules of Coherent Binary Systems
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: Characterization and complexity of uniformly nonprimitive labeled 2-structures