\(k\)-NLC graphs and polynomial algorithms
From MaRDI portal
Publication:1336631
DOI10.1016/0166-218X(94)90026-4zbMath0812.68106OpenAlexW2035344492MaRDI QIDQ1336631
Publication date: 3 November 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(94)90026-4
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items (60)
Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Eigenvalue location in graphs of small clique-width ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ A local characterization of bounded clique-width for line graphs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Characterizations for restricted graphs of NLC-width 2 ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Rank-width: algorithmic and structural results ⋮ Well-quasi-order of relabel functions ⋮ Unnamed Item ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ A SAT Approach to Clique-Width ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Feferman-vaught decompositions for prefix classes of first order logic ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Directed NLC-width ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Constrained-path labellings on graphs of bounded clique-width ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Upper bounds to the clique width of graphs ⋮ Line graphs of bounded clique-width ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Recent developments on graphs of bounded clique-width ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Approximating clique-width and branch-width ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ A model-theoretic characterisation of clique width ⋮ On low rank-width colorings ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ On \textsf{NC} algorithms for problems on bounded rank-width graphs ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Graph operations characterizing rank-width ⋮ Unnamed Item ⋮ Comparing linear width parameters for directed graphs ⋮ The recognizability of sets of graphs is a robust property ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S ⋮ NLC2-DECOMPOSITION IN POLYNOMIAL TIME ⋮ Revising Johnson's table for the 21st century ⋮ On the relationship between NLC-width and linear NLC-width ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ Knocking out \(P_k\)-free graphs ⋮ On algorithms for (\(P_5\), gem)-free 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
This page was built for publication: \(k\)-NLC graphs and polynomial algorithms
