Dense sets and embedding binary trees into hypercubes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004672" target="_blank" >RIV/00216208:11320/07:00004672 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Dense sets and embedding binary trees into hypercubes
Original language description
We describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whosemembers allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.
Czech name
Husté množiny a vnořování binárních stromů do hyperkrychle
Czech description
V článku je popsána metoda vnoření binárních stromů do hyperkrychle, založená na iterativním vnořování do podgrafů indukovaných hustými množinami. Konkrétní aplikací metody je získáno vnoření jisté třídy binárních stromů do jejich optimální hyperkychle sdilatací dva, což představuje částečný výsledek potvrzující hypotézu Bhatta a Ipsenové, podle níž má takové vnoření existovat pro libovolný binární strom.

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

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

Similar results(10)