Recognizing median graphs in subquadratic time

DOI10.1016/S0304-3975(97)00136-9zbMath0913.68152WikidataQ60962151 ScholiaQ60962151MaRDI QIDQ1285576

Johann Hagauer, Sandi Klavžar, Wilfried Imrich

Publication date: 28 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

windexmedian graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Medians in median graphs and their cube complexes in linear time ⋮ The distance spectrum and energy of the compositions of regular graphs ⋮ Computing median and antimedian sets in median graphs ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ Fast recognition algorithms for classes of partial cubes ⋮ An algorithm forK-convex closure and an application ⋮ On the remoteness function in median graphs ⋮ Kazhdan and Haagerup properties from the median viewpoint. ⋮ Recognizing pseudo-median graphs ⋮ A poset-based approach to embedding median graphs in hypercubes and lattices

Cites Work

• A dynamic location problem for graphs
• Medians in median graphs
• The structure of median graphs
• Median graphs and Helly hypergraphs
• Faster isometric embedding in products of complete graphs
• The median procedure on median graphs
• On the complexity of recognizing Hamming graphs and related classes of graphs
• Infinite median graphs, (0, 2)-graphs, and hypercubes
• Metric Ternary Distributive Semi-Lattices
• Retracts of hypercubes
• Graphs Orientable as Distributive Lattices
• n‐cubes and median graphs
• Product graph representations
• Recognizing binary Hamming graphs inO(n 2 logn) time
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item