Algorithm for recognizing Cartesian graph bundles

Zmazek, Blaž; Žerovnik, Janez

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Algorithm for recognizing Cartesian graph bundles
Avtorji:	ID Zmazek, Blaž (Avtor) ID Žerovnik, Janez (Avtor)
Datoteke:	http://dx.doi.org/10.1016/S1571-0653(05)80060-5
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.12 - Objavljeni povzetek znanstvenega prispevka na konferenci
Organizacija:	PEF - Pedagoška fakulteta
Opis:	Graph bundles generalize the notion of covering graphs and graphs products. Authors W. Imrich, T. Pisanski and J. Žerovnik constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base (Discrete Math. 167, 168 (1998) 393-403). The uniquesquare property is defined in Discrete Math., 244 (2002) 551-561, and it is shown that any equivalence relation possesing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define the relation $Delta$ having the unique square property on Cartesian graph bundles over $K_4 setminus e$ -free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over $K_4 setminus e$ -simple base.
Ključne besede:	matematika, teorija grafov, kartezični grafovski svežnji, enolična lokalna produktna lastnost, osnovna faktorizacija, razpoznavanje, polinomski algoritem, mathematics, graph theory, Cartesian graph bundles, unique square property, fundamental factorization, polynomial algorithm, recognition
Leto izida:	1999
Št. strani:	str. 217-221
Številčenje:	Vol. 3
PID:	20.500.12556/DKUM-51506
UDK:	519.17
COBISS.SI-ID:	13823577
ISSN pri članku:	1571-0653
NUK URN:	URN:SI:UM:DK:YKISPYTP
Datum objave v DKUM:	10.07.2015
Število ogledov:	1258
Število prenosov:	95
Metapodatki:
Področja:	Ostalo
:	ZMAZEK, Blaž in ŽEROVNIK, Janez, 1999, Algorithm for recognizing Cartesian graph bundles. V : Electronic notes in discrete mathematics [na spletu]. Objavljeni povzetek znanstvenega prispevka na konferenci. 1999. p. 217–221. [Dostopano 6 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/S1571-0653(05)80060-5 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Electronic notes in discrete mathematics
Založnik:	Elsevier
ISSN:	1571-0653
COBISS.SI-ID:	13803097

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Algoritem za razpoznavanje kartezičnih grafovskih svežnjev
Opis:	Graph bundles generalize the notion of covering graphs and graphs products. Authors W. Imrich, T. Pisanski and J. Žerovnik constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base (Discrete Math. 167, 168 (1998) 393-403). The uniquesquare property is defined in Discrete Math., 244 (2002) 551-561, and it is shown that any equivalence relation possesing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define the relation $Delta$ having the unique square property on Cartesian graph bundles over $K_4 setminus e$ -free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over $K_4 setminus e$ -simple base. Grafovski svežnji predstavljajo posplošitev krovnih in produktnih grafov. V članku vpeljemo enolično lokalno produktno relacijo $Delta$ na kartezičnih svežnjih nad baznimi grafi, ki ne vsebujejo grafa $K_4 setminus e$ in podamo algoritem za razpoznavanje kartezičnih svežnjev nad enostavnimi baznimi grafi brez $K_4 setminus e$ .

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj