On the X-join decomposition for undirected graphs

DOI10.1016/0166-218X(79)90043-XzbMath0439.05041OpenAlexW2003177089MaRDI QIDQ1142232

M. C. Maurer, Michel A. Habib

Publication date: 1979

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

Full work available at URL: https://doi.org/10.1016/0166-218x(79)90043-x

zbMATH Keywords

decompositionsubstitutionjoin of graphslexicographic sumjoin operationR- congruence

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (22)

Decomposition of Directed Graphs ⋮ A \(k\)-structure generalization of the theory of 2-structures ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ On finding the jump number of a partial order by substitution decomposition ⋮ Interval decomposition lattices are balanced ⋮ A linear algorithm to decompose inheritance graphs into modules ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ Unnamed Item ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ Graph classes with and without powers of bounded clique-width ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ A distance measure for large graphs based on prime graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Decomposing complete edge-chromatic graphs and hypergraphs. Revisited ⋮ Modular decomposition and transitive orientation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph derivatives
• Comparability graphs and a new matroid
• A decomposition property of basic acyclic graphs
• On certain polytopes associated with graphs
• Graphs indecomposable with respect to the X-join
• On the composition and decomposition of clutters
• Graph substitution and set packing polytopes
• Transitiv orientierbare Graphen
• The group of an X-join of graphs
• Graph Structures
• Algèbre des relations de congruence

This page was built for publication: On the X-join decomposition for undirected graphs