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

graphalgorithmmatroidsubmodular functionstrength of a graph

Mathematics Subject Classification ID

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

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)