User Tools

Site Tools


Steven Tedford (Franklin and Marshall)

Connectivity in Lifts of Greedoids

Abstract for the Combinatorics Seminar 2006 April 27

A greedoid is an abstract combinatorial structure that captures the essence of the greedy algorithm in combinatorial optimization.

From a given greedoid one can form new ones by a construction called lifting. Theorem: When a greedoid is k-connected, then all of its lifts are, too.

I will introduce greedoids and required background that leads to this result. I will also discuss sufficient and necessary conditions for the lift of an undirected branching greedoid to be two-connected.

seminars/comb/abstract.200604ted.txt · Last modified: 2020/01/29 14:03 (external edit)