An Adjacency-Based Algorithm for Computing Extreme-Supported Efficient Spanning Trees

An adjacency-based algo i hm o compu ing ex eme-suppo ed
e icien spanning ees
Oli e Bach le
join wo k wi h
Felix F i z and S e an Ruzika
RPTU Kaise slau en-Landau
In e na ional Con e ence on Ope a ions Resea ch 2025
MIM
unded by he Deu sche Fo schungsgemeinscha (DFG, Ge man Resea ch Founda ion) - GRK 2982, 516090167 Ma hema ics o In e disciplina y Mul iobjec i e Op imiza ion
Ou line
Basics & Mo i a ion
Mul i-objec i e op imisa ion
Adjacency
A Gene ic Adjacency-Based Algo i hm
Fo global adjacency
Fo a es ic ed neighbou hood
Applica ion o Spanning T ees
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 1 / 14
Mul i-objec i e op imisa ion
De ini ion
Abi-objec i e combina o ial op imisa ion p oblem Πis o he ollowing o m:
min (x)=( 1(x), 2(x))T
s. .x∈X
whe e 1, 2:X→Ra e he objec i e unc ions and Xis ini e. We se Y:= (X).
De ini ion
Fo λ∈(0,1), he weigh ed sum scala isa ion ΠWS(λ)is
min λ 1(x)+(1−λ) 2(x)
s. .x∈X.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 2 / 14
Mul i-objec i e op imisa ion
De ini ion
Abi-objec i e combina o ial op imisa ion p oblem Πis o he ollowing o m:
min (x)=( 1(x), 2(x))T
s. .x∈X
whe e 1, 2:X→Ra e he objec i e unc ions and Xis ini e. We se Y:= (X).
De ini ion
Fo λ∈(0,1), he weigh ed sum scala isa ion ΠWS(λ)is
min λ 1(x)+(1−λ) 2(x)
s. .x∈X.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 2 / 14
A bi-objec i e minimum spanning ee p oblem
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 3 / 14

A bi-objec i e minimum spanning ee p oblem
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 3 / 14
A bi-objec i e minimum spanning ee p oblem
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 3 / 14
A bi-objec i e minimum spanning ee p oblem
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 3 / 14
A bi-objec i e minimum spanning ee p oblem
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 3 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=1
2
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14

Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=1
2
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=1
2
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=1
2
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=4
5
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=2
3
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14

Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
λ=2
3
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Suppo ed solu ions
De ini ion
▶Xλis he se o op imal solu ions o ΠWS(λ).
▶x∈Xλ, o λ∈(0,1), is suppo ed e icien .
▶XSE is he se o suppo ed e icien solu ions.
▶YSN := (XSE )is he se o suppo ed
non-domina ed poin s.
▶The ex eme poin s o con (Y) + R≥and
hei p eimages a e ex eme suppo ed.
▶The co esponding se s a e YESN and XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 4 / 14
Adjacency o easible solu ions
De ini ion
Two spanning ees T,T′o a g aph Ga e
adjacen i hey di e in exac ly one edge.
Adjacency in he li e a u e
▶adjacen basic solu ions
(pa ame ic simplex)
▶ma oid bases di e ing in
one elemen
▶ lows di e ing by a cycle
T1
T2
T3
T4
T7
T5
T8
T6
T9
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 5 / 14

Adjacency o easible solu ions
De ini ion
Two spanning ees T,T′o a g aph Ga e
adjacen i hey di e in exac ly one edge.
Adjacency in he li e a u e
▶adjacen basic solu ions
(pa ame ic simplex)
▶ma oid bases di e ing in
one elemen
▶ lows di e ing by a cycle
T1
T2
T3
T4
T7
T5
T8
T6
T9
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 5 / 14
Adjacency o easible solu ions
De ini ion
Two spanning ees T,T′o a g aph Ga e
adjacen i hey di e in exac ly one edge.
Adjacency in he li e a u e
▶adjacen basic solu ions
(pa ame ic simplex)
▶ma oid bases di e ing in
one elemen
▶ lows di e ing by a cycle
T1
T2
T3
T4
T7
T5
T8
T6
T9
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 5 / 14
Adjacency o easible solu ions
De ini ion
Two spanning ees T,T′o a g aph Ga e
adjacen i hey di e in exac ly one edge.
Adjacency in he li e a u e
▶adjacen basic solu ions
(pa ame ic simplex)
▶ma oid bases di e ing in
one elemen
▶ lows di e ing by a cycle
T1
T2
T3
T4
T7
T5
T8
T6
T9
−
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 5 / 14
Ou line
Basics & Mo i a ion
Mul i-objec i e op imisa ion
Adjacency
A Gene ic Adjacency-Based Algo i hm
Fo global adjacency
Fo a es ic ed neighbou hood
Applica ion o Spanning T ees
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 6 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14

Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
λ=0
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
λ=1
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
λ=8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14

Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
λ=10
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
Ex emely-suppo i e algo i hms
Goal: Compu e YESN.
Why? Because YESN . . .
▶is a good ep esen a ion o YN.
▶is a 2-app oxima ion.
▶con ains a solu ion o ΠWS(λ) o all λ.
De ini ion
An algo i hm is ex emely-suppo i e i i compu es
a se S⊆XESE such ha (S) = YESN .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 7 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14

A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14

A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14
A gene ic ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
No e: By choosing a solu ion ‘maximally o he
le ’ in S ep 4, we ne e need o lea e XESE .246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 8 / 14

An adjacency-based ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14
An adjacency-based ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14
An adjacency-based ex emely-suppo i e algo i hm
Gene ic algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’.
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14
An adjacency-based ex emely-suppo i e algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14
An adjacency-based ex emely-suppo i e algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
X1
3
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14

An adjacency-based ex emely-suppo i e algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
P oblem: Checking lo s o poin s each ime.
Solu ion? Use adjacency and only check
neighbou ing solu ions.
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
X1
3
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 9 / 14
Ou line
Basics & Mo i a ion
Mul i-objec i e op imisa ion
Adjacency
A Gene ic Adjacency-Based Algo i hm
Fo global adjacency
Fo a es ic ed neighbou hood
Applica ion o Spanning T ees
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 10 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
Theo em
The adjacency-based algo i hm is co ec i ,
o all λ∈(0,1)and all x∈Xλ,
▶X<(x)∩Xλ=∅o
▶X<(x)∩Xλcon ains a neighbou o x.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14

Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
e
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
e
e
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Ve i ying he co ec ness c i e ion
Theo em
Le Gbe a g aph and Ta spanning ee such
ha T∈Xλ o some λ∈(0,1). Then
▶X<(T)∩Xλ=∅o
▶X<(T)∩Xλcon ains a neighbou o T.
P oo .
▶Le T∈Xλand T′∈X<(T)∩Xλ.
▶Le e∈T T′and e′∈T′ Tsuch ha
T−e+e′and T′−e′+ea e spanning ees.
▶cλ(e) = cλ(e′).
▶c1(e)>c1(e′)⇒T−e+e′∈X<(T).
▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T).
e
e
e′
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 11 / 14
Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in O(I·nm)
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14

Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in O(I·nm)
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14
Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in O(I·nm)
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14
Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in O(I·nm)
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14
Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in OI·n2m
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14
Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in OI·n2m
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14

Implemen ing he algo i hm
Gene ic adjacency-based algo i hm
1. S a wi h a lexicog aphically op imal
solu ion wi h espec o ( 2, 1).
2. De e mine he slopes o solu ions whose
images a e ‘ o he le ’ and ha a e adjacen .
3. I no such solu ions exis , e mina e.
4. T ansi ion o a solu ion wi h maximal slope.
5. Go o S ep 2.
Theo em
The algo i hm can be implemen ed in O(I·nm)
ime, whe e Iis he numbe o i e a ions.
Implemen a ion
1. Run K uskal’s algo i hm on he
lexicog aphic o de ing.
2. T y all possible exchanges o e∈T
wi h e′/∈Tsuch ha c1(e)>c1(e′).
I i yields a ee, compu e he slope.
3. Check i any solu ion is ound.
4. De e mine he maximum slope.
A small weak
In S ep 2, ind he cycle in T+e′and
swap e′wi h he edges eon he cycle.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 12 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′).
▶|P| ∈ O m2
▶( , ′)∈ P easible i
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s.
0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′).
▶|P| ∈ O m2
▶( , ′)∈ P easible i
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s. 0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′).
▶|P| ∈ O m2
▶( , ′)∈ P easible i
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s. 0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P.
▶|P| ∈ O m2
▶( , ′)∈ P easible i λ≤λ( , ′)
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s.
0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ(e,e′)
λ(e, )λ( ,e′)
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14

Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P.
▶|P| ∈ O m2
▶( , ′)∈ P easible i λ≤λ( , ′)
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s.
0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ(e,e′)
λ(e, )λ( ,e′)
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P.
▶|P| ∈ O m2
▶( , ′)∈ P easible i λ≤λ( , ′)
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s.
0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ(e,e′)
λ(e, )λ( ,e′)
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P.
▶|P| ∈ O m2
▶( , ′)∈ P easible i λ≤λ( , ′)
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s. 0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ(e,e′)
λ(e, )λ( ,e′)
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Bounding he numbe o i e a ions
Theo em
The algo i hm e mina es a e Om2i e a ions.
P oo .
▶T→T−e+e′
▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P.
▶|P| ∈ O m2
▶( , ′)∈ P easible i
▶λ<λ( , ′)o
▶λ=λ( , ′), ∈T, and ′/∈T.
▶A e he ansi ion o T−e+e′ he e a e
ewe easible pai s. 0.2 0.4 0.6 0.8 1
1
2
3
4
e e′
λ(e,e′)
λ(e, )λ( ,e′)
λ
cλ
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 13 / 14
Summa y
We saw how o . . .
▶compu e YESN in an adjacency-based ashion.
▶apply he gene ic algo i hm o spanning ees.
▶bound he numbe o i e a ions.
Fu u e wo k
▶Apply he algo i hm o o he combina o ial
p oblems wi h adjacency concep s.
▶P o e su icien condi ions o ob ain
connec i i y o XSE in gene al.
▶p>2?
Con ac : o.bach le @ma h. p u.de
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 14 / 14

Summa y
We saw how o . . .
▶compu e YESN in an adjacency-based ashion.
▶apply he gene ic algo i hm o spanning ees.
▶bound he numbe o i e a ions.
Fu u e wo k
▶Apply he algo i hm o o he combina o ial
p oblems wi h adjacency concep s.
▶P o e su icien condi ions o ob ain
connec i i y o XSE in gene al.
▶p>2?
Con ac : o.bach le @ma h. p u.de
246
2
4
6
8
10
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 14 / 14
Re e ences I
F i z Bökle and Pe a Mu zel.
T ee-Dele ion P uning in Label-Co ec ing Algo i hms o he Mul iobjec i e Sho es Pa h
P oblem, pages 190–203.
Sp inge In e na ional Publishing, 2017.
C is ina Bazgan, S e an Ruzika, Clemens Thielen, and Daniel Vande poo en.
The powe o he weigh ed sum scala iza ion o app oxima ing mul iobjec i e
op imiza ion p oblems.
Theo y o Compu ing Sys ems, 66(1):395–415, No embe 2021.
Ma hias Eh go .
On ma oids wi h mul iple objec i es.
Op imiza ion, 38(1):73–84, Janua y 1996.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 1 / 2
Re e ences II
Ma hias Eh go .
Mul ic i e ia Op imiza ion.
Numbe 491 in Lec u e No es in Economics and Ma hema ical Sys ems. Sp inge , Be lin,
second edi ion, 2005.
Da id Könen and Michael S iglmay .
An ou pu -polynomial ime algo i hm o de e mine all suppo ed e icien solu ions o
mul i-objec i e in ege ne wo k low p oblems.
Disc e e Applied Ma hema ics, 376:1–14, Decembe 2025.
Se pil Sayın.
Suppo ed nondomina ed poin s as a ep esen a ion o he nondomina ed se : An
empi ical analysis.
Jou nal o Mul i-C i e ia Decision Analysis, 31(1–2), Janua y 2024.
Oli e Bach le An adjacency-based algo i hm o compu ing ex eme-suppo ed e icien spanning ees OR 2025 2 / 2