Publication:3683903
From MaRDI portal
zbMath0567.90073MaRDI QIDQ3683903
Rolf H. Möhring, F. J. Radermacher
Publication date: 1984
Boolean functions; set systems; substitution decomposition; algebraic decomposition theory; combinatorial optimization over graphs
90C35: Programming involving graphs or networks
05C35: Extremal problems in graph theory
90C10: Integer programming
90B35: Deterministic scheduling theory in operations research
05B35: Combinatorial aspects of matroids and geometric lattices
49M27: Decomposition methods
Related Items
A Representation Theorem for Union-Difference Families and Application, Unnamed Item, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Peakless functions on graphs, Bipartite bithreshold graphs, The anti-join composition and polyhedra, On minimal prime extensions of a four-vertex graph in a prime graph, Decomposition of k-ary relations, Almost all comparability graphs are UPO, On algorithms for (\(P_5\), gem)-free graphs, New applications of clique separator decomposition for the maximum weight stable set problem, On the complexity of dynamic programming for sequencing problems with precedence constraints, Circle graphs and monadic second-order logic, Solving some NP-complete problems using split decomposition, The stable set polytope for some extensions of \(P_4\)-free graphs, Critically indecomposable graphs, Structure and stability number of chair-, co-P- and gem-free graphs revisited, A decomposition of distributive lattices, Schedule-induced posets, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Substitution and atomic extension on greedy posets, Asymptotic enumeration of two-dimensional posets, \(P_ 4\)-trees and substitution decomposition, A \(k\)-structure generalization of the theory of 2-structures, On semi-\(P_ 4\)-sparse graphs, Scattering number and modular decomposition, Monadic second-order definable text languages, On the closure of graphs under substitution, A monadic second-order definition of the structure of convex hypergraphs., PC trees and circular-ones arrangements., Stability number of bull- and chair-free graphs revisited, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, The closure of monadic NP, Linear-time modular decomposition of directed graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, Resource-constrained project scheduling: Notation, classification, models, and methods, Recognition of some perfectly orderable graph classes, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, \(N\)-extendible posets, and how to minimize total weighted completion time, On the \(P_4\)-components of graphs, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, The complexity of modular decomposition of Boolean functions, Simple permutations and algebraic generating functions, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Fully dynamic recognition algorithm and certificate for directed cographs, The recognizability of sets of graphs is a robust property, On -sparse graphs and other families, Graph decompositions definable in monadic second-order logic, The bi-join decomposition, Probe Ptolemaic Graphs
