Fast recognition of partial star products and quasi cartesian products

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Fast recognition of partial star products and quasi cartesian products
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)