NLC2-DECOMPOSITION IN POLYNOMIAL TIME

DOI10.1142/S0129054100000223zbMath1320.05124MaRDI QIDQ5249046

Öjvind Johansson

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

graph algebragraph decompositionclique-widthNLC-widthcograph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Characterizations for restricted graphs of NLC-width 2 ⋮ Well-quasi-order of relabel functions ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Line graphs of bounded clique-width ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ On the relationship between NLC-width and linear NLC-width

Cites Work

• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Complement reducible graphs
• \(k\)-NLC graphs and polynomial algorithms
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• A Linear Recognition Algorithm for Cographs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs

This page was built for publication: NLC₂-DECOMPOSITION IN POLYNOMIAL TIME