Fast recognition of subclasses of almost-median graphs
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(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.
Keywords
matematika;teorija grafov;skoraj medianski grafi;algoritem;ne zaključna dela;mathematics;graph theory;almost-median graphs;algorithm;outerplanar graphs;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2007 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
| UDC: | 519.17 |
| COBISS: |
14180697
|
| ISSN: | 0012-365X |
| Views: | 33 |
| Downloads: | 26 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary keywords: | Teorija grafov; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 464-471 |
| Volume: | ǂVol. ǂ307 |
| Issue: | ǂissue ǂ3-5 |
| Chronology: | 2007 |
| DOI: | 10.1016/j.disc.2006.07.011 |
| ID: | 1472909 |
Recommended works:
Fast recognition of subclasses of almost-median graphs
2007,
no subtitle data available
Relations between median graphs, semi-median graphs and partial cubes
1998,
no subtitle data available
On cube-free median graphs
2007,
no subtitle data available
On cube-free median graphs
2003,
no subtitle data available
Partial cubes and their [tau]-graphs
2007,
no subtitle data available