About: Long paths in hypercubes with a quadratic number of faults

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Long paths in hypercubes with a quadratic number of faults Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set of f faulty vertices is called long if its length is at least 2^n-2f-2. We present a function phi(n) = Theta(n^2) such that if f {= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n). Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f {= phi(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length. A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set of f faulty vertices is called long if its length is at least 2^n-2f-2. We present a function phi(n) = Theta(n^2) such that if f {= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n). Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f {= phi(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length. (en)
Title	Long paths in hypercubes with a quadratic number of faults Long paths in hypercubes with a quadratic number of faults (en)
skos:prefLabel	Long paths in hypercubes with a quadratic number of faults Long paths in hypercubes with a quadratic number of faults (en)
skos:notation	RIV/00216208:11320/09:00206366!RIV10-MSM-11320___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1ET100300517), P(1M0545), Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika	21
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Dvořák, Tomáš Koubek, Václav
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	324075
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/09:00206366
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	paths; hypercubes; quadratic; number; faults (en)
http://linked.open.../riv/klicoveSlovo	faults number quadratic paths hypercubes
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[88B239C263AF]
http://linked.open...i/riv/nazevZdroje	Information Sciences
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Methods for Intelligent Systems and Their Applications in Datamining and Natural Language Processing Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	179
http://linked.open...iv/tvurceVysledku	Dvořák, Tomáš Koubek, Václav
http://linked.open...ain/vavai/riv/wos	000269753200003
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0020-0255
number of pages	9 (xsd:int)
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Long paths in hypercubes with a quadratic number of faults Long paths in hypercubes with a quadratic number of faults Long paths in hypercubes with a quadratic number of faults Long paths in hypercubes with a quadratic number of faults

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software