Fast recognition of partial star products and quasi cartesian products

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F15%3A86097346" target="_blank" >RIV/61989100:27240/15:86097346 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Fast recognition of partial star products and quasi cartesian products

Popis výsledku v původním jazyce

This paper is concerned with the fast computation of a relation partial derivative on the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and therecognition of Cartesian graph bundles with a triangle free basis. A special case of partial derivative is the relation delta(+), whose convex closure yields the product relation sigma that induces the prime factor decomposition of connected graphs withrespect to the Cartesian product. For the construction of d so-called Partial Star Products are of particular interest. Several special data structures are used that allow to compute Partial Star Products in constant time. These computations are tuned to the recognition of approximate graph products, but also lead to a linear time algorithm for the computation of delta(+) for graphs with maximum bounded degree. Furthermore, we define quasi Cartesian products as graphs with non-trivial d

Název v anglickém jazyce

Fast recognition of partial star products and quasi cartesian products

Popis výsledku anglicky

This paper is concerned with the fast computation of a relation partial derivative on the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and therecognition of Cartesian graph bundles with a triangle free basis. A special case of partial derivative is the relation delta(+), whose convex closure yields the product relation sigma that induces the prime factor decomposition of connected graphs withrespect to the Cartesian product. For the construction of d so-called Partial Star Products are of particular interest. Several special data structures are used that allow to compute Partial Star Products in constant time. These computations are tuned to the recognition of approximate graph products, but also lead to a linear time algorithm for the computation of delta(+) for graphs with maximum bounded degree. Furthermore, we define quasi Cartesian products as graphs with non-trivial d

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2015

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

Ars Mathematica Contemporanea

ISSN

1855-3966

e-ISSN

—

Svazek periodika

9

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

SI - Slovinská republika

Počet stran výsledku

20

Strana od-do

233-252

Kód UT WoS článku

000352526000007

EID výsledku v databázi Scopus

2-s2.0-84920162866