Fast recognition of subclasses of almost-median graphs

Wilfried Imrich (Avtor), Alenka Lipovec (Avtor), Iztok Peterin (Avtor), Petra Žigert Pleteršek (Avtor)

Povzetek

In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in ▫$O(m\log n)$▫ time, where ▫$n$▫ denotes the number of vertices and ▫$m$▫ the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time.

Ključne besede

matematika;teorija grafov;skoraj medianski grafi;algoritem;ne zaključna dela;mathematics;graph theory;almost-median graphs;algorithm;outerplanar graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	14180697
ISSN:	0012-365X
Št. ogledov:	33
Št. prenosov:	26
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	Teorija grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 464-471
Letnik:	ǂVol. ǂ307
Zvezek:	ǂissue ǂ3-5
Čas izdaje:	2007
DOI:	10.1016/j.disc.2006.07.011
ID:	1472909