Iztok Peterin (Avtor)

Povzetek

Medianski grafi imajo mnogo zanimivih lastnosti. Ena izmed njih je, v povezavi z grafi brez trikotnikov, je časovna zahtevnost za prepoznavanje teh grafov. V splošnem ta zahtevnost ni zelo hitra. Če pa se omejimo na ravninske medianske grafe, je časovna zahtevnost linearna. Kljub temu dejstvu v literaturi ne obstaja karakterizacija ravninskih medianskih grafov. V članku je predstavljen dodaten pogoj h konveksni ekspanziji, ki nam karakterizira ravninske medianske grafe.

Ključne besede

matematika;teorija grafov;medianski grafi;ravninski grafi;ekspanzija;mathematics;graf theory;median graphs;planar graphs;expansion;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17
COBISS: 14034009 Povezava se bo odprla v novem oknu
ISSN: 1234-3099
Št. ogledov: 542
Št. prenosov: 465
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Karakterizacija ravninskih medianskih grafov
Sekundarni povzetek: Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
Sekundarne ključne besede: matematika;teorija grafov;medianski grafi;ravninski grafi;ekspanzija;
URN: URN:SI:UM:
Strani: str. 41-48
Letnik: ǂVol. ǂ26
Zvezek: ǂno. ǂ1
Čas izdaje: 2006
ID: 9595930