Testing connectivity of faulty networks in sublinear time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10100611" target="_blank" >RIV/00216208:11320/12:10100611 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S1570866711001171" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1570866711001171</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Testing connectivity of faulty networks in sublinear time

Popis výsledku v původním jazyce

Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of G - F in polynomial time with respect to |F| and the maximum degree of G. We present two approaches. The first algorithm is designed for graphs with good vertex expansion, while the other solution applies to the class of graphs with cycle basis consisting of cycles of bounded length. We also present an extension of the latter method to test the biconnectivity of G - F.

Název v anglickém jazyce

Testing connectivity of faulty networks in sublinear time

Popis výsledku anglicky

Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of G - F in polynomial time with respect to |F| and the maximum degree of G. We present two approaches. The first algorithm is designed for graphs with good vertex expansion, while the other solution applies to the class of graphs with cycle basis consisting of cycles of bounded length. We also present an extension of the latter method to test the biconnectivity of G - F.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

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

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

14

Číslo periodika v rámci svazku

July 2012

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

223-231

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—