Fast recognition of subclasses of almost-median graphs

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Fast recognition of subclasses of almost-median graphs
Authors:	ID Imrich, Wilfried (Author) ID Lipovec, Alenka (Author) ID Peterin, Iztok (Author) ID Žigert Pleteršek, Petra (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2006.07.011
Language:	English
Work type:	Article
Typology:	1.01 - Original Scientific Article
Organization:	PEF - Faculty of Education
Abstract:	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.
Keywords:	matematika, teorija grafov, skoraj medianski grafi, algoritem, mathematics, graph theory, almost-median graphs, algorithm, outerplanar graphs
Year of publishing:	2007
Number of pages:	str. 464-471
Numbering:	Vol. 307, iss. 3-5
PID:	20.500.12556/DKUM-51566
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	14180697
DOI:	10.1016/j.disc.2006.07.011
NUK URN:	URN:SI:UM:DK:J5MW7BVA
Publication date in DKUM:	10.07.2015
Views:	945
Downloads:	35
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried, LIPOVEC, Alenka, PETERIN, Iztok and ŽIGERT PLETERŠEK, Petra, 2007, Fast recognition of subclasses of almost-median graphs. Discrete mathematics [online]. 2007. Vol. 307, no. 3–5, p. 464–471. [Accessed 28 April 2025]. DOI 10.1016/j.disc.2006.07.011. Retrieved from: http://dx.doi.org/10.1016/j.disc.2006.07.011 Copy citation