Tree-representation of set families and applications to combinatorial decompositions

DOI10.1016/j.ejc.2011.09.032zbMath1239.05130OpenAlexW2044825063MaRDI QIDQ412262

Binh-Minh Bui-Xuan, Michaël Rao, Michel A. Habib

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.09.032

zbMATH Keywords

weakly partitive crossing families

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

Related Items

A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ Algorithmic aspects of switch cographs ⋮ A type of algebraic structure related to sets of intervals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• A complete complexity classification of the role assignment problem
• Theory of 2-structures. II: Representation through labeled tree families
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Decomposition of submodular functions
• Partitive hypergraphs
• Graph minors. X: Obstructions to tree-decomposition
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Minimizing symmetric submodular functions
• PC trees and circular-ones arrangements.
• Branch-width and well-quasi-ordering in matroids and graphs.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A new planarity test
• Approximating clique-width and branch-width
• Unifying the representation of symmetric crossing families and weakly partitive families
• A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
• The bi-join decomposition
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Feedback Vertex Set on Graphs of Low Cliquewidth
• Boolean-Width of Graphs
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• Recognizing circle graphs in polynomial time
• Centroids, Representations, and Submodular Flows
• Regular equivalence: General theory
• A Representation Theorem for Union-Difference Families and Application
• Transitiv orientierbare Graphen
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Tree-representation of set families and applications to combinatorial decompositions