Spectral Bisection with Two Eigenvectors

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F17%3A00477278" target="_blank" >RIV/67985807:_____/17:00477278 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.endm.2017.07.067" target="_blank" >http://dx.doi.org/10.1016/j.endm.2017.07.067</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.endm.2017.07.067" target="_blank" >10.1016/j.endm.2017.07.067</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Spectral Bisection with Two Eigenvectors

Popis výsledku v původním jazyce

We show a spectral bisection algorithm which makes use of the second and third eigenvector of the Laplacian matrix. This algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. To this end, we investigate combinatorial properties of certain configurations of a graph partition. These properties, that we call organized partitions, are shown to be related to the minimality and maximality of a cut. We show that organized partitions are related to the third eigenvector of the Laplacian matrix and give bounds on the minimum cut in terms of organized partitions and eigenvalues.

Název v anglickém jazyce

Spectral Bisection with Two Eigenvectors

Popis výsledku anglicky

We show a spectral bisection algorithm which makes use of the second and third eigenvector of the Laplacian matrix. This algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. To this end, we investigate combinatorial properties of certain configurations of a graph partition. These properties, that we call organized partitions, are shown to be related to the minimality and maximality of a cut. We show that organized partitions are related to the third eigenvector of the Laplacian matrix and give bounds on the minimum cut in terms of organized partitions and eigenvalues.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

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ů

Název periodika

Electronic Notes in Discrete Mathematics

ISSN

1571-0653

e-ISSN

—

Svazek periodika

61

Číslo periodika v rámci svazku

August

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

7

Strana od-do

1019-1025

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85026743217