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

DOI10.1016/J.BULSCI.2008.10.003zbMATH Open1170.68043OpenAlexW2013899012MaRDI QIDQ1004529FDOQ1004529

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

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

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)

Cites Work

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

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)