Greedoids from flames

Autor: Attila Joó
Rok vydání: 2021
Předmět:
Zdroj: Journal of Graph Theory. 98:49-56
ISSN: 1097-0118
0364-9024
DOI: 10.1002/jgt.22681
Popis: A digraph $ D $ with $ r\in V(D) $ is an $ r $-flame if for every $ {v\in V(D)-r} $, the in-degree of $ v $ is equal to the local edge-connectivity $ \lambda_D(r,v) $. We show that for every digraph $ D $ and $ r\in V(D) $, the edge sets of the $ r $-flame subgraphs of $ D $ form a greedoid. Our method yields a new proof of Lovasz' theorem stating: for every digraph $ D $ and $ r\in V(D) $, there is an $ r $-flame subdigraph $ F $ of $ D $ such that $ \lambda_F(r,v) =\lambda_D(r,v) $ for $ v\in V(D)-r $. We also give a strongly polynomial algorithm to find such an $ F $ working with a fractional generalization of Lovasz' theorem.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje