On some algorithmic aspects of hypergraphic matroids

DOI10.1016/j.disc.2022.113222zbMath1504.05050arXiv2111.05699OpenAlexW3212973370MaRDI QIDQ2099466

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Forests, frames, and games: Algorithms for matroid sums and applications
• Separating from the dominant of the spanning tree polytope
• Geometric algorithms and combinatorial optimization.
• A faster algorithm for computing the strength of a network
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On the orientation of graphs and hypergraphs
• Computing minimum multiway cuts in hypergraphs
• Connectivity and edge-disjoint spanning trees
• Network reinforcement
• Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Trees and Cuts
• Optimal attack and reinforcement of a network
• A new approach to the maximum-flow problem
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Computing the Strength of a Graph
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Computing minimum cuts in hypergraphs
• A Fast Parametric Maximum Flow Algorithm and Applications
• Matroids and the greedy algorithm
• Cutsets and partitions of hypergraphs
• Decomposition of Finite Graphs Into Forests