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

DOI10.1016/j.bulsci.2008.10.003zbMath1170.68043OpenAlexW2013899012MaRDI QIDQ1004529

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

algorithmgraphsubmodular functionmatroidstrength of a graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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)

Related Items

Games induced by the partitioning of a graph

Cites Work

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