A Combinatorial Decomposition Theory
From MaRDI portal
Publication:3884147
DOI10.4153/CJM-1980-057-7zbMath0442.05054OpenAlexW2079919815MaRDI QIDQ3884147
Jack Edmonds, William H. Cunningham
Publication date: 1980
Published in: Canadian Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4153/cjm-1980-057-7
Hypergraphs (05C65) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40)
Related Items
Decomposition of Directed Graphs, Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs, Hamilton cycles in plane triangulations, Minimum Cuts and Sparsification in Hypergraphs, A separation decomposition for orders, Spined categories: generalizing tree-width beyond graphs, On the second homology of planar graph braid groups, Circle graph isomorphism in almost linear time, On minimally non-firm binary matrices, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, Digraph Decompositions and Eulerian Systems, Forbidden subgraphs and graph decomposition, Connected hyperplanes in binary matroids, Unnamed Item, Cluster Editing: Kernelization Based on Edge Cuts, Graph isomorphism restricted by lists, A polynomial kernel for distance-hereditary vertex deletion, A Representation Theorem for Union-Difference Families and Application, On the Complexity of Matroid Isomorphism Problems, Unifying the representation of symmetric crossing families and weakly partitive families, Graph decompositions definable in monadic second-order logic, Two disjoint negative cycles in a signed graph, Tree Pivot-Minors and Linear Rank-Width, Nonseparating Cocircuits in Binary Matroids, The graph sandwich problem for 1-join composition is NP-complete, A \(k\)-structure generalization of the theory of 2-structures, Decomposition of 3-connected graphs, An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs, On chains of 3-connected matroids, Bicircular matroids representable over \(\mathrm{GF}(4)\) or \(\mathrm{GF}(5)\), Two representations of finite ordered sets, Detecting 2-joins faster, The arborescence-realization problem, N-free posets as generalizations of series-parallel posets, An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs, Decomposition of wheel-and-parachute-free balanced bipartite graphs, A decomposition theory for matroids. V: Testing of matrix total unimodularity, The incidence structure of subspaces with well-scaled frames, Bounding and stabilizing realizations of biased graphs with a fixed group, Self-dual graphs, 3-connected reduction for regular graph covers, The structure of 3-connected matroids of path width three, The structure of the 3-separations of 3-connected matroids. II., Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Reconstruction of infinite matroids from their 3-connected minors, A supernodal formulation of vertex colouring with applications in course timetabling, On polygon numbers of circle graphs and distance hereditary graphs, Axioms for infinite matroids, Local 2-separators, Characteristics of graph braid groups, Jordan-like characterization of automorphism groups of planar graphs, The structure of 2-separations of infinite matroids, Tree-representation of set families and applications to combinatorial decompositions, Decomposition of 3-connected representable matroids, Stability, fragility, and Rota's conjecture, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Counting labelled three-connected and homeomorphically irreducible two- connected graphs, Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs, Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs, Graph theory. Abstracts from the workshop held January 2--8, 2022, Two-sided combinatorial volume bounds for non-obtuse hyperbolic polyhedra, Local convergence of random planar graphs, Hepp's bound for Feynman graphs and matroids, Balanced matrices, Many 2-level polytopes from matroids, Completely separable graphs, On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, On the complexity of matroid isomorphism problem, Partitive hypergraphs, Decomposition of partial orders, Separating cocircuits in binary matroids, A survey of the algorithmic aspects of modular decomposition, The structure of the 4-separations in 4-connected matroids, 2-clique-bond of stable set polyhedra, The structure of crossing separations in matroids, Practical and efficient split decomposition via graph-labelled trees, Computing \(H\)-joins with application to 2-modular decomposition, Edge bipartization faster than \(2^k\), Constructive characterizations of 3-connected matroids of path width three, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, On complexities of minus domination, Decomposition of 3-connected cubic graphs, The decomposition of graphs into \(k\)-connected components, Tutte polynomials computable in polynomial time, Connectivity of submodular functions, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Cluster editing: kernelization based on edge cuts, Distance-hereditary comparability graphs, Ghost symmetry and an analogue of Steinitz's theorem, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, Rigidity, global rigidity, and graph decomposition, The structure of the 3-separations of 3-connected matroids, Compositions for perfect graphs, Basic perfect graphs and their extensions, On the 2-sum in rigidity matroids, Minimum balanced bipartitions of planar triangulations, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Hamiltonian properties of polyhedra with few 3-cuts. A survey, A matroid invariant via the \(K\)-theory of the Grassmannian, Decomposition of k-ary relations, Structure and enumeration of two-connected graphs with prescribed three-connected components, Treelike comparability graphs, The Tutte polynomial of a ported matroid, Canonical decompositions of symmetric submodular systems, On Computing the Gromov Hyperbolicity, On separability: Functional structure, Characterizing matroids whose bases form graphic delta-matroids, On testing consecutive-ones property in parallel, The family of bicircular matroids closed under duality, Decomposition of balanced matrices, Subdivisional spaces and graph braid groups, The graphs that have antivoltages using groups of small order, Some remarks on Jaeger's dual-hamiltonian conjecture, The structure of equivalent 3-separations in a 3-connected matroid, Decomposition of submodular functions, Balanced \(0,\pm 1\) matrices. I: Decomposition, A decomposition of distributive lattices, A decomposition theory for matroids. I: General results, 1-intersecting families, Quasi-star-cutsets and some consequences, Connectivity in bicircular matroids, Knocking out \(P_k\)-free graphs
