Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F02%3A00073311" target="_blank" >RIV/49777513:23520/02:00073311 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/49777513:23520/02:00000408
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
Popis výsledku v původním jazyce
The well-known greedy algorithm MIN for finding a maximal independent set in a graph Gis based on recursively removing the closed neighborhood of a vertex which has (in the currently existing graph) minimum degree. We give a forbidden induced subgraph condition under which algorithm MIN always results in finding a maximum independent set of G, and hence yields the exact value of the independence number of G in polynomial time.
Název v anglickém jazyce
Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
Popis výsledku anglicky
The well-known greedy algorithm MIN for finding a maximal independent set in a graph Gis based on recursively removing the closed neighborhood of a vertex which has (in the currently existing graph) minimum degree. We give a forbidden induced subgraph condition under which algorithm MIN always results in finding a maximum independent set of G, and hence yields the exact value of the independence number of G in polynomial time.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—

Rok uplatnění
2002
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)