Node-to-Set Disjoint Paths Problem in a Mobius Cube

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F16%3A00338688" target="_blank" >RIV/68407700:21240/16:00338688 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1587/transinf.2015EDP7331" target="_blank" >https://doi.org/10.1587/transinf.2015EDP7331</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1587/transinf.2015EDP7331" target="_blank" >10.1587/transinf.2015EDP7331</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Node-to-Set Disjoint Paths Problem in a Mobius Cube

Popis výsledku v původním jazyce

This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Mobius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n(4)), and the maximum path length, 2n - 1. A computer experiment is conducted for n = 1, 2, ... , 31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n(3)) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

Název v anglickém jazyce

Node-to-Set Disjoint Paths Problem in a Mobius Cube

Popis výsledku anglicky

This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Mobius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n(4)), and the maximum path length, 2n - 1. A computer experiment is conducted for n = 1, 2, ... , 31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n(3)) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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

IEICE Transactions on Information and Systems

ISSN

0916-8532

e-ISSN

1745-1361

Svazek periodika

E99D

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

JP - Japonsko

Počet stran výsledku

6

Strana od-do

708-713

Kód UT WoS článku

000375973400017

EID výsledku v databázi Scopus

—