Algoritmo di Kernighan-Lin

Algoritmo di Kernighan-Lin
Classe	Grafi
Struttura dati	grafico ponderato
Caso peggiore temporalmente	O(n^2 \log n)
Manuale

L'algoritmo Kernighan–Lin è un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessità computazionale $O(n^{2}\log n)$ .

Questo algoritmo, proposto nel 1970 da Shen Lin e Brian Kernighan, ha importanti applicazioni per la progettazione di circuiti digitali e VLSI.

Descrizione

Si consideri il grafo $G=(V,E)$ , dove $V$ denota l'insieme dei vertici ed $E$ l'insieme degli archi.

L'algoritmo mira a trovare una partizione di $V$ in due sottoinsiemi $A$ e $B$ di uguale cardinalità, tali che la somma $T$ del costo degli archi fra elementi di $A$ e $B$ sia minimizzato.

In particolare, se si denota con

I_{a}

il costo interno di

a

(cioè la somma del costo degli archi fra

a

e altri elementi che sono nello stesso sottoinsieme, sia esso

A

B

)

E_{a}

il costo esterno (cioè la somma del costo degli archi fra

a

e tutti gli altri vertici che non appartengono al medesimo insieme di

a

)

D_{a}=E_{a}-I_{a}

la differenza di costo

Allora si ha che se si scambiano due elementi $a$ e $b$ (uno appartenente ad $A$ , l'altro a $B$ ), si ha una riduzione di costo

T_{vecchio}-T_{nuovo}=D_{a}+D_{b}-2c_{a,b}

dove con $c_{a,b}$ si denota il costo dell'arco fra $a$ e $b$ .

L'algoritmo cerca una sequenza ottimale di permutazioni di un elemento di $A$ e uno di $B$ tale da massimizzare $T_{vecchio}-T_{nuovo}$ .^[1] its one of the optimized algorithms.

Pseudocodice

Vedi^[2]

 1  function Kernighan-Lin(G(V,E)):
 2      determina una partizione iniziale dei vertici in A e B
 3      do
 4         A1 := A; B1 := B
 5         calcola D per tutti gli a in A1 e b in B1
 6         for (i := 1 to |V|/2)
 7            trova a[i] da A1 e b[i] da B1 tali che g[i] = D[a[i] ] + D[b[i] ] - 2*c[a[i] ][b[i] ] è massimale
 8            sposta a[i] a B1 e b[i] ad A1
 9            tralascia a[i] e b[i] da ulteriori considerazioni
 10           aggiorna i valori di D per gli elementi di A1 = A1 /{a[i]} and B1 = B1 /{b[i]}
 11        end for
 12        trova k che massimizza g_max=g[1] + ... +g[k]
 13        if (g_max > 0) then
 14           Scambia a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
 15     until (g_max <= 0)
 16  return G(V,E)

Note

^ B. W. Kernighan e Shen Lin, An efficient heuristic procedure for partitioning graphs, in Bell Systems Technical Journal, vol. 49, 1970, pp. 291–307.
^ Si. Pi Ravikumār, Ravikumar, C.P, Parallel methods for VLSI layout design, Greenwood Publishing Group, 1995, p. 73, ISBN 978-0-89391-828-6, OCLC 2009-06-12.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

Read other articles:

Cnemaspis

Cnemaspis Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Subfilum: Vertebrata Kelas: Reptilia Ordo: Squamata Subordo: Lacertilia Famili: Gekkonidae Genus: CnemaspisStrauch, 1887[1] Cnemaspis adalah marga kelompok cecak liar yang bertubuh relatif kecil dan umumnya aktif di siang hari (diurnal). Cecak ini tersebar luas di Asia Selatan, Asia Tenggara, hingga kepulauan Nusantara. Populasi di Afrika, yang sebelumnya dianggap sebagai bagian dari marga ini, terbukti merupakan anggota...

Juan Manuel Lillo

Juan Manuel Lillo Informasi pribadiNama lengkap Juan Manuel Lillo DíezTanggal lahir 3 November 1965 (umur 58)Tempat lahir Tolosa, SpanyolKepelatihanTahun Tim 1981–1985 Amaroz KE1985–1988 Tolosa1988–1989 Mirandés1990–1991 Mirandés1991–1992 Cultural Leonesa1992–1996 Salamanca1996–1997 Oviedo1998 Tenerife2000 Zaragoza2003–2004 Ciudad Murcia2004–2005 Terrassa2005–2006 Dorados Sinaloa2008–2009 Real Sociedad2009–2010 Almería2014 Millonarios2015–2016 Chile (assist...

Festival Lagu Populer Jakarta 1976

Festival Lagu Populer Jakarta 1976Kompilasi karya Various ArtistDirilis1976Direkam?GenrePopDurasi?LabelPramaquaProduser-Series Festival Lagu Populer Indonesia 1975 (1975)'Festival Lagu Populer Indonesia 1975'1975 Festival Lagu Populer Jakarta 1976 (1976) Festival Lagu Populer Jakarta 1977 (1977)'Festival Lagu Populer Jakarta 1977'1977 Festival Lagu Populer Jakarta 1976 adalah Album kompilasi Festival Lagu Populer tingkat Jakarta ke III yang dirilis pada tahun 1976. Lagu wajib dalam festiv...

CACNB1

Protein-coding gene in the species Homo sapiens CACNB1IdentifiersAliasesCACNB1, CAB1, CACNLB1, CCHLB1, calcium voltage-gated channel auxiliary subunit beta 1External IDsOMIM: 114207 MGI: 102522 HomoloGene: 20186 GeneCards: CACNB1 Gene location (Human)Chr.Chromosome 17 (human)[1]Band17q12Start39,173,453 bp[1]End39,197,703 bp[1]Gene location (Mouse)Chr.Chromosome 11 (mouse)[2]Band11 D|11 61.5 cMStart97,892,334 bp[2]End97,913,860 bp[2]RNA expr...

2014 European Parliament election in Austria

2014 European Parliament election in Austria ← 2009 25 May 2014 2019 → All 18 Austrian seats to the European ParliamentTurnout45.39% (0.58pp) First party Second party Third party Leader Othmar Karas Eugen Freund Harald Vilimsky Party ÖVP SPÖ FPÖ Alliance EPP PES EAF Last election 29.98%, 6 seats 23.74%, 5 seats 12.71%, 2 seats Seats won 5 5 4 Seat change 1 2 Popular vote 761,896 680,180 556,835 Percentage 26.98% 24.09% 19.72% ...

Wilhelm Hertenstein

Wilhelm Hertenstein Anggota Dewan Federal SwissMasa jabatan21 Maret 1879 – 27 November 1888PendahuluJohann Jakob SchererPenggantiWalter HauserPresiden Konfederasi Swiss Ke-40Masa jabatan1 Januari 1888 – 27 November 1888PendahuluNuma DrozPenggantiBernhard Hammer Informasi pribadiLahir(1825-05-05)5 Mei 1825Kyburg, Zürich, SwissMeninggal27 November 1888(1888-11-27) (umur 63)Bern, SwissSunting kotak info • L • B Wilhelm Friederich Hertenstein (5 Mei 1825&...

The Big Parade

Untuk film Tionghoa tahun 1986 bernama sama, lihat The Big Parade (film 1986). Untuk epsiode Dad's Army, lihat The Big Parade (Dad's Army). The Big ParadePoster rilis layar lebarSutradaraKing VidorProduserKing Vidor (dipersembahkan oleh)Irving Thalberg (tak disebutkan)Ditulis olehHarry BehnJoseph W. FarnhamBerdasarkanPlumesnovel autobiografi tahun 1925oleh Laurence StallingsPemeran John Gilbert Renée Adorée Hobart Bosworth Tom O'Brien Karl Dane Penata musikWilliam AxtDavid MendozaSine...

Baruch Samuel Blumberg

Baruch Samuel BlumbergBaruch Samuel BlumbergLahir28 Juli, 1925Meninggal5 April, 2011KebangsaanAmerika SerikatDikenal atasVirus Hepatitis BPenghargaan1976 Penghargaan Nobel dalam Fisiologi atau Kedokteran dr. Baruch Samuel Blumberg (28 Juli 1925- – 5 April 2011[[Kategori:Meninggal usia Kesalahan ekspresi: Operand tak ditemukan untuk -]]) adalah ilmuwan Amerika Serikat yang memenangkan Hadiah Nobel Fisiologi atau Kedokteran tahun 1976 karena keberhasilannya menemukan vaksin Hep...

Gammarth

Town in Tunis Governorate, TunisiaGammarthTownAerial view of the coastlineGammarthCoordinates: - 25000) 36°54′35″N 10°17′12″E / 36.90972°N 10.28667°E / 36.90972; 10.28667Country TunisiaGovernorateTunis GovernoratePopulation (2023) • Total15,000 - 25,000Time zoneUTC+1 (CET) Gammarth (Tunisian Arabic: ڨمرت gāmmartⓘ) is a town on the Mediterranean Sea in the Tunis Governorate of Tunisia, located some 15 to 20 kilometres north of Tu...

Porto di Gioia Tauro

Porto di Gioia TauroPanoramica del porto di Gioia TauroStato Italia Regione Calabria Provincia Reggio Calabria ComuneGioia Tauro e San Ferdinando MareMar Tirreno Infrastrutture collegateAutostrada A2, Aeroporto di Lamezia Terme, Aeroporto di Reggio Calabria, Ferrovia Tirrenica Meridionale TipoPorto commerciale e industriale GestoriAutorità di Sistema Portuale dei Mari Tirreno Meridionale e Ionio Profondità fondalida 14,5 a 18,00 m Rifornimento carburanteSì AssistenzaSì...

متلازمة XXXX

متلازمة XXXX معلومات عامة الاختصاص علم الوراثة الطبية تعديل مصدري - تعديل رباعي X ويعرف أيضًا باسم XXXX ‏,48، هو اضطراب صبغي حيث يكون لدى الأنثى أربعة صبغيات X بدلاً من الاثنين النموذجيين. ترتبط هذه الحالة بدرجات متفاوتة من الإعاقة الذهنية، وملامح الوجه المميزة التي تتمي...

Actinidia deliciosa

Species of plant Actinidia deliciosa Kiwifruit Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Asterids Order: Ericales Family: Actinidiaceae Genus: Actinidia Species: A. deliciosa Binomial name Actinidia deliciosa(A.Chev.) C.F.Liang & A.R.Ferguson Synonyms Actinidia chinensis var deliciosa (A.Chev.) A.Chev. Actinidia deliciosa, the fuzzy kiwifruit, is a fruiting vine native to Southern China. Other species of Actinidia are al...

Stirling Gardens

Park in Perth, Western Australia Stirling GardensStirling GardensTypeUrban parkLocationPerth, Western AustraliaCoordinates31°57′23″S 115°51′36″E / 31.9565°S 115.86°E / -31.9565; 115.86Created1845EtymologyNamed after James StirlingOperated byCity of PerthStatusOpen 1890s postcard showing Stirling Gardens with the Old Treasury Buildings (then the General Post Office) across St Georges Tce in the background Stirling Gardens is a small public park in Perth...

Strong Poison

1930 mystery novel by Dorothy L. Sayers Strong Poison First editionAuthorDorothy L. SayersCountryUnited KingdomLanguageEnglishSeriesLord Peter WimseyGenreMystery novelPublisherGollancz[1]Publication date1930[1]Media typePrintPages288[1]Preceded byThe Unpleasantness at the Bellona Club Followed byThe Five Red Herrings Strong Poison is a 1930 mystery novel by Dorothy L. Sayers, her fifth featuring Lord Peter Wimsey and the first in which Harriet...

Brushfire Records

Brushfire RecordsParent companyUniversal Music GroupFounded2002 (2002)FounderJack JohnsonEmmett MalloyDistributor(s)Republic Records(in the US)Virgin EMI Records(in the UK)GenreRock, popCountry of originU.S.LocationLos Angeles, CaliforniaOfficial websitebrushfirerecords.com Brushfire Records is a record label owned by singer-songwriter Jack Johnson. Formerly known as The Moonshine Conspiracy Records, the label was founded to release soundtracks for Woodshed Films, a company owned by John...

January 30, 1961 State of the Union Address

Speech by US president John F. Kennedy January 30, 1961, State of the Union AddressDateJanuary 30, 1961 (1961-01-30)Duration43 minutes[1]VenueHouse Chamber, United States CapitolLocationWashington, D.C.Coordinates38°53′23″N 77°00′32″W / 38.88972°N 77.00889°W / 38.88972; -77.00889TypeState of the Union AddressParticipantsJohn F. KennedyLyndon B. JohnsonSam RayburnPreviousJanuary 12, 1961, State of the Union AddressNext1962 State of the...

Dassault Mirage 5

French attack/interceptor aircraft Mirage 5 Chilean Air Force Mirage 5MA Role Attack aircraft Fighter-bomberType of aircraft National origin France Manufacturer Dassault Aviation First flight 19 May 1967 Status Active Primary users French Air Force (historical)Belgian Air Force (historical) Egyptian Air Force Pakistan Air Force Number built 582 Developed from Dassault Mirage III Variants IAI Nesher Developed into IAI Kfir The Dassault Mirage 5 is a French supersonic attack aircraft/fight...

Daftar bahasa di Sumatra

Sebaran bahasa di Sumatra bagian Utara Sebaran bahasa batak di Sumatra Ragam bahasa Lampung di Sumatra bagian selatan, hijau: Lampung Api, merah: Lampung Nyo, biru: Komering Daftar bahasa di Sumatra adalah daftar bahasa pribumi yang tersebar di pulau Sumatra (Indonesia) beserta kode bahasa masing-masing menurut pengkodean bahasa ISO 639-3 dan kode bahasa BPS. Nama bahasa Kode bahasa ISO 639-3 Kode bahasa BPS Bahasa Abung abl Bahasa Aceh ace ach Bahasa Alas-Kluet btz als Bahasa Bangka mfb Baha...

David Bautista

Pour les articles homonymes, voir Bautista (homonymie). David Bautista David Bautista à la GalaxyCon de 2019. Données clés Nom de naissance David Michael Bautista Jr. Naissance 18 janvier 1969 (55 ans)Washington, D.C. (États-Unis) Nationalité Américaine Profession Acteur Films notables Les Gardiens de la Galaxie (saga)007 SpectreUnivers cinématographique MarvelDuneGlass Onion : Une histoire à couteaux tirés modifier David BautistaBatista en tant que catcheur.Données gén�...

Gillis Valckenier

Burgomaster of Amsterdam Gillis ValckenierGillis Valckenier (1671) by Wallerant VaillantRegent and Mayor of AmsterdamIn office1665–1679Preceded byAndries de GraeffSucceeded byJohannes Hudde Personal detailsBorn1623AmsterdamDied1680AmsterdamNationalityDutchPolitical partyPrince of Orange factionOccupationRegent / Mayor Gillis Valckenier (1623–1680) was nine years burgomaster of Amsterdam: in 1665, 1666, 1668, 1670, 1673, 1674, 1676, 1678, 1679. He had a strong personality, but changed alli...