Structural and Algorithmic Properties Concerning Packing, Covering and Partitioning of Digraphs

Yun Wang*

*Kontaktforfatter

Publikation: AfhandlingPh.d.-afhandling

Abstract

I denne afhandling giver vi en fuldstændig klassifikation af de semikomplette digrafer, der har et udspændende ud-træ med rod u, som er kant-disjunkt fra mindst et udspændende ind-træ med rod v, hvor u, v er foreskrevne knuder. S˚adan et par kaldes et godt (u, v)-par. Ved hjælp af denne karaktersation løser vi fuldstændigt problemet med at afgøre, om en given digraf, som er opn˚aet ved at substituere punkterne i en semikomplet digraf med arbitrære digrafer, har et godt (u, v)-par for givne punkter u, v. Dette løser et ˚abent problem af Bang-Jensen og Gutin fra 1998 vedrørende gode par i kvasi-transitive digrafer. Vi beskriver ogs˚a flere resultater vedrørende eksistensen af gode par i digrafer hvis komplement er 2-delt.

Derudover studerer vi problemet med at opdele kanterne i en splitdigraf D i to disjunkte delmængder som begge inducerer en stærkt sammenhængende udspændende digraf af D. Vi beviser blandt andet, at enhver 3-kant-sammenhængende splitdigraf har en s˚adan kantdekomponering. Dette bekræfter en generel formodning af Bang-Jensen og Yeo om kantdekomponering i stærkt sammenhængende udspændende deldigrafer i digrafer med høj kant-sammenhængsgrad for specialtilfældet hvor digrafen er en splitdigraf. Vi beskriver ogs˚a en uendelig klasse af 2-stærke splitdigrafer, som ikke har et godt (u, v)-par for mindst et valgt af u og v. Vores resultater bekræfter at Thomassens formodning om eksistensen af gode (u, v)-par i digrafer med høj kant-sammenhæng gælder for de fem klasser af digrafer nævnt ovenfor med kant-sammenhæng 3.

Hvis en digraf D har et godt (u, v)-par, s˚a gælder det for hvert punkt w af D, at D har en (w, v)-vej, som er kant-disjunkt fra mindst et udspændende ud-træ med rod u. Det viser sig, at dette delproblem ogs˚a har en meget naturlig karakterisation for semikomplette digrafer. I karakterisationen af semikomplette digrafer med et godt (u, v)-par for givne knuder u, v spiller eksistensen af kant-disjunkte (s1, t1)- og (s2, t2)-veje en vigtig rolle. Motiveret af dette, studerer vi i afhandlingen ogs˚a problemet med at finde kant-disjunkte veje med specificerede endepunkter i semikomplete digrafer og udvider dette studie til ogs˚a at omhandle s˚akaldte blandede grafer (eng:mixed graphs).

Et andet emne i denne afhandling omhandler strukturelle og algoritmiske egenskaber af generaliserede veje og kredse i semikomplette mangedelte digrafer. Vi viser, hvordan disse resultater giver os mulighed for at identificere polynomielt løsbare instanser af det orienterede TSP problem med 0-1 vægte, s˚avel som andre instanser, hvor vi kan vi kan komme meget tæt p˚a den optimale løsning i polynomiel tid. Alle vores beviser i afhandlingen er konstruktive og kan konverteres til polynomielle algoritmer. 
OriginalsprogEngelsk
Bevilgende institution
  • Syddansk Universitet
Vejledere/rådgivere
  • Bang-Jensen, Jørgen, Hovedvejleder
Dato for forsvar2. feb. 2024
Udgiver
DOI
StatusUdgivet - 17. jan. 2024

Note vedr. afhandling

Afhandlingen kan læses på SDUs bibliotek.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Structural and Algorithmic Properties Concerning Packing, Covering and Partitioning of Digraphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater