Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs

DOI10.1016/j.dam.2012.03.034zbMath1245.05058OpenAlexW2078658343MaRDI QIDQ444440

Mikhail N. Vyalyi, Vladimir A. Gurvich

Publication date: 14 August 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.034

zbMATH Keywords

distanceminimum cutspanning treemaximum flowultrametricdecomposing \(n\)-graphsGomoryHu treepositional gamewidest bottleneck path

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Directed graphs (digraphs), tournaments (05C20) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (21)

Weak similarities of finite ultrametric and semimetric spaces ⋮ Metric and ultrametric inequalities for directed graphs ⋮ Minimum spanning paths and Hausdorff distance in finite ultrametric spaces ⋮ On \(p\)-metric spaces and the \(p\)-Gromov-Hausdorff distance ⋮ How rigid the finite ultrametric spaces can be? ⋮ Labeled trees generating complete, compact, and discrete ultrametric spaces ⋮ Uniqueness of best proximity pairs and rigidity of semimetric spaces ⋮ Bipartite graphs and best proximity pairs ⋮ Hereditary properties of finite ultrametric spaces ⋮ Resistance distance in connected balanced digraphs ⋮ On the Gomory-Hu inequality ⋮ On ultrametric-preserving functions ⋮ On spaces extremal for the Gomory-Hu inequality ⋮ Combinatorial properties of ultrametrics and generalized ultrametrics ⋮ Finite ultrametric balls ⋮ The range of ultrametrics, compactness, and separability ⋮ On some extremal properties of finite ultrametric spaces ⋮ Ultrametric preserving functions and weak similarities of ultrametric spaces ⋮ On quasisymmetric mappings between ultrametric spaces ⋮ From isomorphic rooted trees to isometric ultrametric spaces ⋮ Properties and morphisms of finite ultrametric spaces and their representing trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Not complementary connected and not CIS \(d\)-graphs form weakly monotone families
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• The directed subgraph homeomorphism problem
• On a universal ultrametric space
• Trees as semilattices
• On graphs whose maximal cliques and stable sets intersect
• The category of ultrametric spaces is isomorphic to the category of complete, atomic, tree-like, and real graduated lattices LAT\(^*\)
• Proximity on equilateral spaces
• Maximal Flow Through a Network
• On Cartesian Trees and Range Minimum Queries
• Multi-Terminal Network Flows
• Counting Minimum Weight Spanning Trees
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Metric and ultrametric spaces of resistances
• Metric and ultrametric spaces of resistances
• Encyclopedia of Distances

This page was built for publication: Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs