Sketchy Notes on Edmonds’ Incredible Shrinking Blossom Algorithm for General Matching
Download
1.17 Mb.
Page
10/19
Date
02.05.2018
Size
1.17 Mb.
#47336
1
...
6
7
8
9
10
11
12
13
...
19
has one iff
does. Thus we need consider only the case in which the base of the blossom is free.
Suppose
has an augmenting path. Either this
path is an augmenting path in
or it ends at the blossom
, and it can be extended
to an augmenting path in
by following the blossom in the direction that results in alternation until reaching the base.
Suppose
has an augmenting path. Either
it is an augmenting path in
or it hits the blossom
, in which case the part from one end until the blossom is first
hit is an augmenting path in
Directory:
courses
->
archive
courses -> San José State University Social Science/Psychology Psych 175, Management Psychology, Section 1, Spring 2014
courses -> Kennan's Telegram (Excerpt)
courses -> The university of british columbia
courses -> A hurricane track density function and empirical orthogonal function approach to predicting seasonal hurricane activity in the Atlantic Basin Elinor Keith April 17, 2007 Abstract
courses -> Cover page need figure & title by Proposed Table of Contents
courses -> Objectives
courses -> Dr. Jeff Masters' WunderBlog
archive -> Cos 423 Problem Set 6 Due Tuesday May 10, 2011
archive -> Cos 423 Problem Set No. 5-revised Due Wed. April 23, 2003 Spring 2003
Download
1.17 Mb.
Share with your friends:
1
...
6
7
8
9
10
11
12
13
...
19
The database is protected by copyright ©ininet.org 2024
send message
Main page
Guide
Instructions
Report
Request
Review
does. Thus we need consider only the case in which the base of the blossom is free.
by following the blossom in the direction that results in alternation until reaching the base.
