scientific article
From MaRDI portal
Publication:3683903
zbMath0567.90073MaRDI QIDQ3683903
F. J. Radermacher, Rolf H. Möhring
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boolean functionsset systemssubstitution decompositionalgebraic decomposition theorycombinatorial optimization over graphs
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Combinatorial aspects of matroids and geometric lattices (05B35) Decomposition methods (49M27)
Related Items
Combining decomposition approaches for the maximum weight stable set problem, Modular decomposition of hypergraphs, Symmetric maximal Condorcet domains, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, Cograph editing: Merging modules is equivalent to editing P_4s, A tight lower bound for primitivity in k-structures, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, A Representation Theorem for Union-Difference Families and Application, Unnamed Item, Schedule-induced posets, A \(k\)-structure generalization of the theory of 2-structures, An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Existential MSO over two successors is strictly weaker than over linear orders, Interval decomposition lattices are balanced, Definable transductions and weighted logics for texts, On independent vertex sets in subclasses of apple-free graphs, An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, On semi-\(P_ 4\)-sparse graphs, Scattering number and modular decomposition, Substitution and atomic extension on greedy posets, The complexity of modular decomposition of Boolean functions, Monadic second-order definable text languages, Arc-Disjoint Paths in Decomposable Digraphs, New applications of clique separator decomposition for the maximum weight stable set problem, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, On the closure of graphs under substitution, Asymptotic enumeration of two-dimensional posets, Resolutions of convex geometries, More results on weighted independent domination, A supernodal formulation of vertex colouring with applications in course timetabling, An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem, A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs, Complete edge-colored permutation graphs, (Nearly-)tight bounds on the contiguity and linearity of cographs, Graph reconstruction in the congested clique, Tree-representation of set families and applications to combinatorial decompositions, A monadic second-order definition of the structure of convex hypergraphs., Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time, PC trees and circular-ones arrangements., Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Simple permutations and algebraic generating functions, Probe Ptolemaic Graphs, Stability number of bull- and chair-free graphs revisited, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, Counting spanning trees using modular decomposition, Fully dynamic representations of interval graphs, A survey of the algorithmic aspects of modular decomposition, \(N\)-extendible posets, and how to minimize total weighted completion time, On the complexity of dynamic programming for sequencing problems with precedence constraints, An \(O(n^2)\) time algorithm for the minimal permutation completion problem, Recognition of prime graphs from a prime subgraph, Practical and efficient split decomposition via graph-labelled trees, On the \(P_4\)-components of graphs, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, Characterization and complexity of uniformly nonprimitive labeled 2-structures, An efficient exact algorithm for triangle listing in large graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Circle graphs and monadic second-order logic, Solving some NP-complete problems using split decomposition, Peakless functions on graphs, The minimum weakly connected independent set problem: polyhedral results and branch-and-cut, Bipartite bithreshold graphs, The anti-join composition and polyhedra, \(P_ 4\)-trees and substitution decomposition, An algorithm computing combinatorial specifications of permutation classes, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, Single machine scheduling with precedence constraints and positionally dependent processing times, On probe permutation graphs, Linear-time modular decomposition of directed graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, \(O(m\log n)\) split decomposition of strongly-connected graphs, On minimal prime extensions of a four-vertex graph in a prime graph, The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Applying modular decomposition to parameterized cluster editing problems, On distance-3 matchings and induced matchings, Fully dynamic recognition algorithm and certificate for directed cographs, Cluster Editing: Kernelization Based on Edge Cuts, Reconstructing gene trees from Fitch's xenology relation, The stable set polytope for some extensions of \(P_4\)-free graphs, Critically indecomposable graphs, Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Resource-constrained project scheduling: Notation, classification, models, and methods, Recognition of some perfectly orderable graph classes, Decomposition of k-ary relations, Algorithmic aspects of a general modular decomposition theory, Modular decomposition of graphs and the distance preserving property, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Maximum weight independent sets in hole- and co-chair-free graphs, On Distance-3 Matchings and Induced Matchings, O(m logn) Split Decomposition of Strongly Connected Graphs, Grundy dominating sequences on \(X\)-join product, The closure of monadic NP, The recognizability of sets of graphs is a robust property, Miscellaneous Digraph Classes, Unifying the representation of symmetric crossing families and weakly partitive families, Almost all comparability graphs are UPO, A decomposition of distributive lattices, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., On -sparse graphs and other families, Graph decompositions definable in monadic second-order logic, The bi-join decomposition, Unavoidable induced subgraphs in large graphs with no homogeneous sets, On algorithms for (\(P_5\), gem)-free graphs
