Algorithm for recognizing Cartesian graph bundles

Blaž Zmazek (Avtor), Janez Žerovnik (Avtor)

Povzetek

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$▫.

Ključne besede

matematika;teorija grafov;kartezični grafovski svežnji;enolična lokalna produktna lastnost;osnovna faktorizacija;razpoznavanje;polinomski algoritem;ne zaključna dela;mathematics;graph theory;Cartesian graph bundles;unique square property;fundamental factorization;polynomial algorithm;recognition;

Podatki

Jezik:	Angleški jezik
Leto izida:	1999
Tipologija:	1.12 - Objavljeni povzetek znanstvenega prispevka na konferenci
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	13823577
ISSN:	1571-0653
Št. ogledov:	1097
Št. prenosov:	90
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Algoritem za razpoznavanje kartezičnih grafovskih svežnjev
Sekundarni povzetek:	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.
Sekundarne ključne besede:	Teorija grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Članek v reviji
Strani:	str. 217-221
Zvezek:	ǂVol. ǂ3
Čas izdaje:	May 1999
DOI:	10.1016/S1571-0653(05)80060-5
ID:	1472583