scientific article; zbMATH DE number 1472167

MaRDI QIDQ4489221zbMATH OpenFDO

Authors Öjvind Johansson

Publication date 17 October 2000

zbMATH Keywords

decompositionrandom graphvertex-labeled graphswidth

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• NLC\(_{2}\)-decomposition in polynomial time
• scientific article; zbMATH DE number 1420903
• On the Boolean-width of a graph: structure and applications
• scientific article; zbMATH DE number 2044940
• Grammars and clique-width bounds from split decompositions

Cited in

(37)

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Graph operations characterizing rank-width
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Computing the clique-width of cactus graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Knocking out \(P_k\)-free graphs
• Rank-width: algorithmic and structural results
• Bounding clique-width via perfect graphs
• Line graphs of bounded clique-width
• Vertex disjoint paths on clique-width bounded graphs
• A model-theoretic characterisation of clique width
• On the relationship between NLC-width and linear NLC-width
• Steiner trees for hereditary graph classes: a treewidth perspective
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• Bounding clique-width via perfect graphs
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• On the Boolean-width of a graph: structure and applications
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Polynomial-time recognition of clique-width 3 graphs
• On switching classes, NLC-width, cliquewidth and treewidth
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)
• Clique-width for graph classes closed under complementation
• The behavior of clique-width under graph operations and graph transformations
• Definable decompositions for graphs of bounded linear cliquewidth
• Bounding the mim‐width of hereditary graph classes
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Bounding the Mim-Width of Hereditary Graph Classes.
• Word-representable graphs and locality of words
• Boolean-width of graphs
• A local characterization of bounded clique-width for line graphs
• Graph classes with and without powers of bounded clique-width
• Directed NLC-width
• On a disparity between relative cliquewidth and relative NLC-width
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Clique-width of graphs defined by one-vertex extensions

This page was built for publication:

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