On some algorithmic aspects of hypergraphic matroids

DOI10.1016/J.DISC.2022.113222MaRDI QIDQ2099466zbMATH OpenOpenAlexFDO

Authors Mourad Baïou, Francisco Barahona

Publication date 23 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.05699

zbMATH Keywords

combinatorial optimizationhypergraphic matroidsnetwork reinforcement

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Abstract: Hypergraphics matroids were studied first by Lorea and later by Frank et al. They can be seen as generalizations of graphic matroids. Here we show that several algorithms developed for the graphic case can be extended to hypergraphic matroids. We treat the following: the separation problem for the associated polytope, testing independence, separation of partition inequalities, computing the rank of a set, computing the strength, computing the arboricity and network reinforcement.

Recommendations

• Recognizing Polymatroids Associated with Hypergraphs
• A note on the separation problem for the matching matroid
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Hypergraphic submodular function minimization
• Publication:4886037

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• A faster algorithm for computing the strength of a network
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• A new approach to the maximum-flow problem
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Computing minimum cuts in hypergraphs
• Computing minimum multiway cuts in hypergraphs
• Computing the Strength of a Graph
• Connectivity and edge-disjoint spanning trees
• Cutsets and partitions of hypergraphs
• Decomposition of Finite Graphs Into Forests
• Edge-Disjoint Spanning Trees of Finite Graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 3512137 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Matroids and the greedy algorithm
• Network reinforcement
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On the orientation of graphs and hypergraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal attack and reinforcement of a network
• Separating from the dominant of the spanning tree polytope
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Trees and Cuts

Cited in

(10)

• A matroid view of key theorems for edge-swapping algorithms
• Sprague-Grundy function of matroids and related hypergraphs
• On the heterochromatic number of hypergraphs associated to geometric graphs and to matroids
• The Algorithmic Aspects of Uncrowded Hypergraphs
• Recognizing Polymatroids Associated with Hypergraphs
• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• Finding branch-decompositions of matroids, hypergraphs, and more
• On some partial line graphs of a hypergraph and the associated matroid
• An algorithm for packing hypertrees
• Modulus of hypertrees

This page was built for publication: On some algorithmic aspects of hypergraphic matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099466)