Computing the fully optimal spanning tree of an ordered bipolar directed graph

DOI10.1016/j.disc.2024.113895arXiv1807.06552OpenAlexW2883292267WikidataQ128542127 ScholiaQ128542127MaRDI QIDQ6204322

Emeric Gioan, Michel Las Vergnas

Publication date: 27 March 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.06552

zbMATH Keywords

computational complexitylinear programmingspanning treeTutte polynomialactive bijectionbipolar directed graph

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• The active bijection for graphs
• The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
• Geometric algorithms and combinatorial optimization
• Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids
• The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
• Activity preserving bijections between spanning trees and orientations in graphs
• A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements
• Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Oriented Matroids
• Digraphs
• A higher invariant for matroids
• A Contribution to the Theory of Chromatic Polynomials
• The Tutte polynomial of oriented matroids

This page was built for publication: Computing the fully optimal spanning tree of an ordered bipolar directed graph