Stable (théorie des graphes)

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Pour les articles homonymes, voir stable.

En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient.

Propriétés combinatoires

La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G). On appelle carré d'un graphe G le graphe G' utilisant les mêmes sommets et ayant une arête entre deux sommets u et v si et seulement s'il existe un chemin de longueur au plus 2 entre u et v dans G. Alors I(G') est inférieure ou égale à dom(G)^[1].

Problème algorithmique

La recherche d'un stable de taille maximum dans un graphe est un problème classique de la théorie de la complexité. Il est NP-complet et difficile à approximer^[2].

Notes et références

↑ (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
↑ Voir article détaillé.

Read other articles:

Università statale del Michigan

Questa voce sugli argomenti università degli Stati Uniti d'America e Michigan è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Michigan State UniversityUniversità statale del Michigan UbicazioneStato Stati Uniti CittàEast Lansing, Michigan Dati generaliMotto'Advancing Knowledge.Transforming Lives' Fondazione1855 Tipopubblica RettoreDr. Lou Anna Simon Studenti46 648 (2009) Dipendenti6 166 (2009) Colori Verde e Bianco AffiliazioniAAU Sp...

Hari Upah Setara

Bendera Hari Gaji Setara berkibar pada 21 Maret 2014 di Alsbach, JermanHari Gaji Setara adalah hari simbolik yang didedikasikan kepada kesadaran akan ketimpangan gaji gender. Di Amerika Serikat, tanggal tersebut melambagkan bagaimana dalam setahun rata-rata wanita harus bekerja dalam rangka meraih raihan rata-rata pria pada tahun sebelumnya tanpa memandang pengalaman atau jenis kerja. Tangga pastinya berbeda dari tahun ke tahun.[1] Referensi ^ Equal Pay Day. www.pay-equity.org. Diarsi...

Aktivin dan inhibin

inhibin, alphaPengidentifikasiSimbolINHAGen NCBI3623HGNC6065OMIM147380RefSeqNM_002191UniProtP05111Data lainLokusChr. 2 q33-qterPencarianStrukturSwiss-modelDomainInterPro inhibin, beta AThe Activin dimer, from 2ARV.pdbPengidentifikasiSimbolINHBASimbol alternatifactivin AGen NCBI3624HGNC6066OMIM147290RefSeqNM_002192UniProtP08476Data lainLokusChr. 7 p15-p13PencarianStrukturSwiss-modelDomainInterPro inhibin, beta BPengidentifikasiSimbolINHBBSimbol alternatifactivin BGen NCBI3625HGNC6067...

Ronald Sanderson

British rower Olympic medal record Men's rowing 1908 London Eight Memorial to Ronald Harcourt Sanderson in Ripon Cathedral Lieutenant Colonel Ronald Harcourt Sanderson (11 December 1876 – 17 April 1918) was an English rower who competed in the 1908 Summer Olympics for Great Britain.[1] He was killed in action during the First World War.[2] Early life and rowing career Sanderson was born at Uckfield, Sussex, the only son of Rev. Edward Sanderson of Uckfield. He was educated a...

Stacking velocity

Seismological concept This article appears to be a dictionary definition. Please rewrite it to present the subject from an encyclopedic point of view. (May 2023) In reflection seismology, stacking velocity, or Normal Moveout (NMO) velocity, is the value of the seismic velocity obtained from the best fit of the traveltime curve by a hyperbola.[1][failed verification]. The hyperbolic approximation to the traveltime curve (two-way travel time versus offset) is known as Normal mov...

Jennie Franks

British actor, playwright and photographer Jennie Franks is an English playwright and filmmaker. Jennie Franks Career Franks co-wrote and directed an educational film about the effects of AIDS in rural Colorado titled Soft Smoke, AIDS in the Rural West.[1][2] She wrote and acted in the play Stuck!, about one woman's courageous struggle to get out of a locked basement bathroom at a coffee house and reclaim control of her stalled life, which debuted in New York in 2008.[3 ...

Sport in Taiwan

Overview of sports in Taiwan This article is about sport in Taiwan (Republic of China). For sport in the People's Republic of China, see Sport in China. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Sport in Taiwan – news · newspapers · books · scholar · JSTOR (November 2007) (Learn how and when to remove ...

Rambu peringatan

Pameran sebagian besar tanda peringatan (dengan beberapa tanda pengaturan seperti Dilarang Masuk), Museum Otomotif Torino Bentuk dan warna tanda peringatan yang dipakai: Memakai Memakai Memakai Memakai Memakai , sebelumnya memakai Tidak ada informasi Tanda peringatan adalah sebuah jenis tanda yang mengisyaratkan sebuah bahaya, rintangan atau kondisi potensial yang mengharuskan perhatian khusus. Beberapa adalah rambu...

This Gift (song)

This GiftSingle by 98 Degreesfrom the album This Christmas Released1999Length4:08LabelUniversalSongwriter(s)Anders BaggeArnthor BirgissonDane DevillerSean Hosein98 Degrees singles chronology I Do (Cherish You) (1999) This Gift (1999) Thank God I Found You (2000) This Gift is the first single released by American boy band 98 Degrees from their third studio album, This Christmas. It was written by Anders Bagge, Arnthor Birgisson, Dane Deviller, and Sean Hosein and released during Christmastime...

乌克兰总理

烏克蘭總理Прем'єр-міністр України烏克蘭國徽現任杰尼斯·什米加尔自2020年3月4日任命者烏克蘭總統任期總統任命首任維托爾德·福金设立1991年11月后继职位無网站www.kmu.gov.ua/control/en/（英文）乌克兰乌克兰政府与政治系列条目宪法政府总统弗拉基米尔·泽连斯基總統辦公室国家安全与国防事务委员会总统代表（英语：Representatives of the President of Ukraine）总...

Стахановский трамвай

Стахановский трамвай Описание Страна Украина Расположение Стаханов, Ирмино, Алмазная Дата открытия 1937 Дата закрытия 2008 Маршрутная сеть Число маршрутов 0 Самый длинный маршрут Стаханов — Ирмино Подвижной состав Число вагонов 0 Число вагонов в период макс. развития 38 Ч...

الثروة الحيوانية (الدواجن)

الثروة الحيوانية (الدواجن) (بالإنجليزية: (poultry) Animal Wealth) هي كل ما نمتلكه من موارد توفر لنا البروتين الحيواني أو اللحوم بشكل عام ويمكن تقسيم الثروة الحيوانية كالآتي: حيوانات المزرعة: الإبل، الأبقار، الأغنام، الماعز. الدواجن: الدجاج (بياض، لاحم)، الرومي، البط والأوز، والحمام و�...

Crystal monochromator

Device for selecting radiation wavelengths This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Crystal monochromator – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message) Neutron monochromator for the ECHIDNA powder diffractometer at OPAL in Australia. It is made by slabs of [11...

كاسحة ألغام (سفينة)

هذه المقالة عن السفينة البحرية. لمعانٍ أخرى، طالع كانسة الألغام (توضيح). كانسة ألغام في خليج المكسيك في 12 يوليو 1944 كانسة الألغام أو كاسحة الألغام[1] هي سفينة حربية بحرية صغيرة مصممة لتدمير الألغام البحرية. باستخدام آليات مختلفة تهدف إلى مواجهة التهديد الذي تشكله ا...

Tell It Like It Is (George Benson album)

1969 studio album by George BensonTell It Like It IsStudio album by George BensonReleasedMid/End of July 1969[1]RecordedApril 29, 1969 (#6–7, 9)May 16, 1969 (#1–5)May 20, 1969 (#8, 10–11)StudioVan Gelder Studio, Englewood Cliffs, NJGenreJazzLength32:27LabelA&M/CTISP 3020ProducerCreed TaylorGeorge Benson chronology Goodies(1968) Tell It Like It Is(1969) The Other Side of Abbey Road(1970) Tell It Like It Is is the seventh album by American guitarist George Benson featu...

Referéndum republicano de Sudáfrica de 1960

• 1983 → Referéndum republicano de Sudáfrica¿Está a favor de una República para la Unión?[1] Fecha 5 de octubre de 1960 Tipo Referéndum Demografía electoral Población 17 396 Hab. registrados 1800 Votantes 1634 Participación 90.77 % Votos válidos 1626 (99,52 %) Votos nulos 7904 (0,48 %) Resultados República Votos 850,458 ̴...

Ismail Khan

Afghan politician and former warlord (born 1946) For the Pashto singer from Pakistan, see Ismail and Junaid. Ismail KhanIsmail Khan at the 2010 National Conference on Water Resources, Development and Management of AfghanistanMinister of Energy and WaterIn office2004 – October 2013PresidentHamid KarzaiSucceeded byMohammad Arif NoorzaiGovernor of Herat ProvinceIn office2001 – 12 September 2004PresidentHamid KarzaiPreceded byMulla Yaar MohammadSucceeded bySayed Mohammad Kha...

Colata in sabbia

Stampo per colata in sabbia (aperto) Esempio di manufatti in bronzo (a sinistra) e in alluminio (a destra) di una colata in sabbia La colata in sabbia è un processo di produzione industriale del tipo fusione. La prima fase consiste nella creazione di un modello di materiali vari, attorno a cui sarà costruita la forma. Solitamente, è previsto un piano di simmetria per l'apertura corretta della stessa senza danneggiare il modello. Approntata la forma, con tutte le necessarie anime e incavi p...

Religión en Argentina

Religión en Argentina (2023)Religión[1] Catolicismo (48%) Sin religión (25%) Protestantismo (10%) Otros cristianos (5%) Otras religiones (5%) Prefiere no decirlo (8%) La religión en Argentina se practica en el marco de la libertad de culto garantizada por el artículo 14 de la Constitución Nacional, aun...

William Tell (1825 play)

1825 play William TellWritten byJames Sheridan KnowlesDate premiered11 May 1825Place premieredTheatre Royal, Drury Lane, LondonOriginal languageEnglishGenreHistoricalSettingSwitzerland, 14th century William Tell is an 1825 historical play by the Irish writer James Sheridan Knowles. It portrays the legendary 14th-century Swiss folk hero William Tell in his battle against the Habsburg authorities.[1] It premiered at the Theatre Royal, Drury Lane in London. The original cast starred Will...