Fast recognition algorithms for classes of partial cubes

DOI10.1016/S0166-218X(02)00416-XzbMath1022.05050OpenAlexW2169134983MaRDI QIDQ1408812

Boštjan Brešar, Wilfried Imrich, Sandi Klavžar

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00416-x

zbMATH Keywords

complexityalgorithmhypercubeisometric subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Computing median and antimedian sets in median graphs ⋮ Fast recognition of classes of almost-median graphs ⋮ Characterizing almost-median graphs ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Omega Polynomial in Nanostructures ⋮ Projection of a medium ⋮ Characterizing almost-median graphs. II. ⋮ A characterization of planar partial cubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isometric embedding in products of complete graphs
• The structure of median graphs
• A convexity lemma and expansion procedures for bipartite graphs
• Recognizing median graphs in subquadratic time
• Recognizing graphs of acyclic cubical complexes
• Graphs of acyclic cubical complexes
• Distance-preserving subgraphs of hypercubes
• Arboricity and Subgraph Listing Algorithms
• Median Graphs and Triangle-Free Graphs
• Quasi‐median graphs and algebras
• Tiled partial cubes
• Isometric subgraphs of Hamming graphs and d-convexity
• Recognizing binary Hamming graphs inO(n 2 logn) time
• On the Addressing Problem for Loop Switching

This page was built for publication: Fast recognition algorithms for classes of partial cubes