\(k\)-NLC graphs and polynomial algorithms

DOI10.1016/0166-218X(94)90026-4zbMath0812.68106MaRDI QIDQ1336631

Egon Wanke

Publication date: 3 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(k\)-node label controlled graphs; Hamiltonian circuit property; simple max-cut problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

Related Items

Inductive computations on graphs defined by clique-width expressions, GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Algorithmic uses of the Feferman-Vaught theorem, On algorithms for (\(P_5\), gem)-free graphs, Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, Vertex-minors, monadic second-order logic, and a conjecture by Seese, A local characterization of bounded clique-width for line graphs, Characterizations for restricted graphs of NLC-width 2, Clique-width of graphs defined by one-vertex extensions, The NLC-width and clique-width for powers of graphs of bounded tree-width, Graph operations characterizing rank-width, Edge dominating set and colorings on graphs with fixed clique-width, Upper bounds to the clique width of graphs, On powers of graphs of bounded NLC-width (clique-width), Line graphs of bounded clique-width, Approximating clique-width and branch-width, Linear layouts measuring neighbourhoods in graphs, Vertex disjoint paths on clique-width bounded graphs, A model-theoretic characterisation of clique width, The recognizability of sets of graphs is a robust property, On the relationship between NLC-width and linear NLC-width, On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract), Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, The Clique-Width of Tree-Power and Leaf-Power Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Graph grammars with neighbourhood-controlled embedding
• On simple characterizations of k-trees
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Dacey Graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• A linear time algorithm for finding tree-decompositions of small treewidth