A new algorithm for the intersection of a line with the independent set polytope of a matroid

DOI10.1016/J.BULSCI.2008.10.003MaRDI QIDQ1004529zbMATH OpenOpenAlexFDO

Authors Alexandre Skoda

Publication date 11 March 2009

Published in Bulletin des Sciences Mathématiques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.bulsci.2008.10.003

zbMATH Keywords

algorithmgraphmatroidstrength of a graphsubmodular function

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 4068895
• Two algorithms for weighted matroid intersection
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• scientific article; zbMATH DE number 3904606
• A Fast Approximation for Maximum Weight Matroid Intersection

Cites work

• A faster algorithm for computing the strength of a network
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Computing the Strength of a Graph
• Connectivity and edge-disjoint spanning trees
• Matroids and the greedy algorithm
• Network reinforcement
• Optimal attack and reinforcement of a network
• Separating from the dominant of the spanning tree polytope
• Submodular functions and optimization.
• Testing membership in matroid polyhedra

Cited in

(1)

• Games induced by the partitioning of a graph

This page was built for publication: A new algorithm for the intersection of a line with the independent set polytope of a matroid

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