Fast recognition algorithms for classes of partial cubes

DOI10.1016/S0166-218X(02)00416-XMaRDI QIDQ1408812zbMATH OpenOpenAlexFDO

Authors 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

algorithmcomplexityhypercubeisometric subgraph

Mathematics Subject Classification ID

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

Recommendations

• Recognizing partial cubes in quadratic time
• Partial cubes: Structures, characterizations, and constructions
• Fast recognition of classes of almost-median graphs
• Partial cubes and their \(\tau\)-graphs
• Partial cubes as subdivision graphs and as generalized Petersen graphs

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• scientific article; zbMATH DE number 15874 (Why is no real title available?)
• scientific article; zbMATH DE number 165070 (Why is no real title available?)
• scientific article; zbMATH DE number 1339499 (Why is no real title available?)
• scientific article; zbMATH DE number 653263 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• A convexity lemma and expansion procedures for bipartite graphs
• Arboricity and Subgraph Listing Algorithms
• Distance-preserving subgraphs of hypercubes
• Graphs of acyclic cubical complexes
• Isometric embedding in products of complete graphs
• Isometric subgraphs of Hamming graphs and d-convexity
• Median Graphs and Triangle-Free Graphs
• On the Addressing Problem for Loop Switching
• Quasi‐median graphs and algebras
• Recognizing binary Hamming graphs inO(n 2 logn) time
• Recognizing graphs of acyclic cubical complexes
• Recognizing median graphs in subquadratic time
• The structure of median graphs
• Tiled partial cubes

Cited in

(15)

• Fast recognition of classes of almost-median graphs
• A characterization of planar partial cubes
• Characterizing almost-median graphs
• Tree-like isometric subgraphs of hypercubes
• Computing median and antimedian sets in median graphs
• Complexity of phylogenetic networks: Counting cubes in median graphs and related problems
• Partial cubes and their \(\tau\)-graphs
• Recognizing halved cubes in a constant time per edge
• Tiled partial cubes
• Characterizing almost-median graphs. II.
• Omega polynomial in nanostructures
• On partial cubes, well-graded families and their duals with some applications in graphs
• Recognizing partial cubes in quadratic time
• Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
• Projection of a medium

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1408812)