k-NLC graphs and polynomial algorithms

DOI10.1016/0166-218X(94)90026-4zbMATH Open0812.68106OpenAlexW2035344492WikidataQ131632916 ScholiaQ131632916MaRDI QIDQ1336631FDOQ1336631

Egon Wanke

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

zbMATH Keywords

\(k\)-node label controlled graphsHamiltonian circuit propertysimple max-cut problem

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

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

Cited In (63)

• Title not available (Why is that?)
• Fast FPT-approximation of branchwidth
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(b\)-coloring parameterized by clique-width
• Locating Eigenvalues of Symmetric Matrices - A Survey
• Inductive computations on graphs defined by clique-width expressions
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• Directed NLC-width
• Feferman-vaught decompositions for prefix classes of first order logic
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• On low rank-width colorings
• Efficient parameterized algorithms for computing all-pairs shortest paths
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• Algorithmic uses of the Feferman-Vaught theorem
• Digraphs of Bounded Width
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• On switching classes, NLC-width, cliquewidth and treewidth
• Vertex disjoint paths on clique-width bounded graphs
• On a disparity between relative cliquewidth and relative NLC-width
• Recent developments on graphs of bounded clique-width
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Constrained-path labellings on graphs of bounded clique-width
• Eigenvalue location in graphs of small clique-width
• Edge dominating set and colorings on graphs with fixed clique-width
• Knocking out \(P_k\)-free graphs
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• On powers of graphs of bounded NLC-width (clique-width)
• A local characterization of bounded clique-width for line graphs
• Comparing linear width parameters for directed graphs
• Upper bounds to the clique width of graphs
• Well-quasi-order of relabel functions
• On algorithms for (\(P_5\), gem)-free graphs
• The most vital nodes with respect to independent set and vertex cover
• A SAT Approach to Clique-Width
• Line graphs of bounded clique-width
• Characterizations for restricted graphs of NLC-width 2
• Graph operations characterizing rank-width
• 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
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Rank-width: algorithmic and structural results
• The recognizability of sets of graphs is a robust property
• A model-theoretic characterisation of clique width
• Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• On the relationship between NLC-width and linear NLC-width
• On \textsf{NC} algorithms for problems on bounded rank-width graphs
• Linear Clique‐Width for Hereditary Classes of Cographs
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Clique-width of graphs defined by one-vertex extensions
• Title not available (Why is that?)
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• The behavior of clique-width under graph operations and graph transformations
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
• \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs
• Revising Johnson's table for the 21st century
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S

This page was built for publication: \(k\)-NLC graphs and polynomial algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336631)