Fast recognition of subclasses of almost-median graphs

Imrich, Wilfried; Lipovec, Alenka; Peterin, Iztok; Žigert Pleteršek, Petra

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Fast recognition of subclasses of almost-median graphs
Avtorji:	ID Imrich, Wilfried (Avtor) ID Lipovec, Alenka (Avtor) ID Peterin, Iztok (Avtor) ID Žigert Pleteršek, Petra (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2006.07.011
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	PEF - Pedagoška fakulteta
Opis:	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(mlog 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, mathematics, graph theory, almost-median graphs, algorithm, outerplanar graphs
Leto izida:	2007
Št. strani:	str. 464-471
Številčenje:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51566
UDK:	519.17
COBISS.SI-ID:	14180697
DOI:	10.1016/j.disc.2006.07.011
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:J5MW7BVA
Datum objave v DKUM:	10.07.2015
Število ogledov:	945
Število prenosov:	35
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried, LIPOVEC, Alenka, PETERIN, Iztok in ŽIGERT PLETERŠEK, Petra, 2007, Fast recognition of subclasses of almost-median graphs. Discrete mathematics [na spletu]. 2007. Vol. 307, no. 3–5, p. 464–471. [Dostopano 27 april 2025]. DOI 10.1016/j.disc.2006.07.011. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2006.07.011 Kopiraj citat