A
median graph G
is a graph where, for any three vertices
u
,
v
and
w
, there is a unique node that lies on a shortest path from
u
to
v
, from
u
to
w
, and from
v
to
w
. While not obvious from the ...definition, median graphs are
partial cubes
; that is, they can be isometrically embedded in hypercubes and, consequently, in integer lattices. The
isometric
and
lattice dimensions
of
G
, denoted as
dim
I
(
G
) and
dim
Z
(
G
), are the smallest integers
k
and
r
so that
G
can be isometrically embedded in the
k
-dimensional hypercube and the
r
-dimensional lattice respectively. Motivated by recent results on the cover graphs of distributive lattices, we study these parameters through
median semilattices
, a class of ordered structures related to median graphs. We show that not only does this approach provide new combinatorial characterizations for
dim
I
(
G
) and
dim
Z
(
G
), they also have nice algorithmic consequences. Assume
G
has
n
vertices and
m
edges. We prove that
dim
I
(
G
) can be computed in
O
(
n
+
m
) time, and an isometric embedding of
G
on a hypercube with dimension
dim
I
(
G
) can be constructed in
O
(
n
×
dim
I
(
G
)) time. The algorithms are extremely simple and the running times are optimal. We also show that
dim
Z
(
G
) can be computed and an isometric embedding of
G
on a lattice with dimension
dim
Z
(
G
) can be constructed in
time by using an existing algorithm of Eppstein’s that performs the same tasks for partial cubes. We are able to speed up his algorithm by using our framework to provide a new “interpretation” to the algorithm. In particular, we note that its main part is essentially a generalization of Fulkerson’s method for finding a smallest-sized chain decomposition of a poset.
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.
For stable marriage (SM) and solvable stable roommates (SR) instances, it is known that there are stable matchings that assign each participant to his or her (lower/upper) median stable partner. ...Moreover, for SM instances, a stable matching has this property if and only if it is a median of the distributive lattice formed by the instance's stable matchings. In this paper, we show that the above local/global median phenomenon first observed in SM stable matchings also extends to SR stable matchings because SR stable matchings form a median graph. In the course of our investigations, we also prove that three seemingly different structures are pairwise duals of each other--median graphs give rise to mirror posets and vice versa, and mirror posets give rise to SR stable matchings and vice versa. Together, they imply that for every median graph G with n vertices, there is an SR instance I(G) with O(...) participants whose graph of stable matchings is isomorphic to G. Our results are analogous to the pairwise duality results known for distributive lattices, posets, and SM stable matchings. Interestingly, some of these results can also be inferred from the work of Feder in the early 1990s. Our constructions and proofs, however, are more natural generalizations of those used for SM instances. PUBLICATION ABSTRACT
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks ...become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented.
Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a ...fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph
G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in
G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.
Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a ...fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph
G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in
G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.
A quasi-median graph can be characterized as a weak retract of a Cartesian product of complete graphs or equivalently as a graph of finite windex. We derive a new characterization of quasi-median ...graphs which allows us to recognize these graphs in O(n√n log n+m log n) time. It is shown that skeletons of quasi-median graphs are median graphs. For an arbitrary vertex s an s-skeleton of a graph is obtained from G by deleting all edges uv that satisfy d(u, s) = d(v, s). As a by-product of this approach the size of a maximum complete subgraph of a quasi-median graph can be computed within the same time bound. Furthermore, we show that the distance matrix of a quasi-median graph can be computed in O(n
2
).
PDF
