A Fast Algorithm for the Decomposition of Graphs and Posets

DOI10.1287/MOOR.8.2.170zbMath0517.05057OpenAlexW2014488291MaRDI QIDQ3665151

Hermann Buer, Rolf H. Möhring

Publication date: 1983

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.8.2.170

zbMATH Keywords

combinatorial optimizationdecomposition of graphsautonomous subsets

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial aspects of partitions of integers (05A17) Permutations, words, matrices (05A05) Graph theory (05C99)

Related Items (39)

Decomposition of Directed Graphs ⋮ A combinatorial bijection between linear extensions of equivalent orders ⋮ 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 ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ On transitive orientations with restricted covering graphs ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Scattering number and modular decomposition ⋮ Indecomposable graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Minimizing bumps in ordered sets by substitution decomposition ⋮ The dimension of graphs with respect to the direct powers of a two-element graph ⋮ Weighted parameters in \((P_5,\overline {P_5})\)-free graphs ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ The discrete time-cost tradeoff problem revisited ⋮ A continuous rating method for preferential voting: the complete case ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Dynamic labeled 2-structures ⋮ Decomposition of infinite labeled 2-structures ⋮ On the complexity of dynamic programming for sequencing problems with precedence constraints ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Theory of 2-structures ⋮ Group based graph transformations and hierarchical representations of graphs ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times ⋮ Decomposing complete edge-chromatic graphs and hypergraphs. Revisited ⋮ Applying modular decomposition to parameterized cluster editing problems ⋮ Critically indecomposable graphs ⋮ Optimal procedures for the discrete time/cost trade-off problem in project networks ⋮ Unnamed Item ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S ⋮ Modular decomposition and transitive orientation ⋮ Almost all comparability graphs are UPO ⋮ A decomposition of distributive lattices ⋮ Nonpreemptive scheduling of independent tasks with prespecified processor allocations ⋮ An algorithm for minimizing setups in precedence constrained scheduling ⋮ Incremental construction of 2-structures

This page was built for publication: A Fast Algorithm for the Decomposition of Graphs and Posets