𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recognizing median graphs in subquadratic time

✍ Scribed by Johann Hagauer; Wilfried Imrich; Sandi Klavžar

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
1018 KB
Volume
215
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Medians in median graphs
Medians in median graphs
✍ H.J. Bandelt; J.P. Barthélemy 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 668 KB
Recognizing Hamming graphs in linear tim
Recognizing Hamming graphs in linear time and space
✍ Wilfried Imrich; Sandi Klavžar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 417 KB

Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorab

Recognizing string graphs in NP
Recognizing string graphs in NP
✍ Marcus Schaefer; Eric Sedgwick; Daniel Štefankovič 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 219 KB

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP: The recognition problem was not known to be decidable u

Invariant Hamming graphs in infinite qua
Invariant Hamming graphs in infinite quasi-median graphs
✍ Marc Chastand; Norbert Polat 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 593 KB

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming g