All Questions
4 questions
1
vote
0
answers
88
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
3
votes
1
answer
240
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 33
5
votes
1
answer
238
views
Do the Odd Cycles of a Graph Define a Matroid?
An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.
Question:
does the collection of "critical" sets of vertices, whose removal renders a ...
- 13.2k
13
votes
1
answer
2k
views
Menger's theorem via matroids
Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...
- 109k