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

DOI10.1016/j.dam.2012.03.034zbMath1245.05058MaRDI 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

distance; minimum cut; spanning tree; maximum flow; ultrametric; decomposing \(n\)-graphs; Gomory; Hu tree; positional game; widest bottleneck path

Mathematics Subject Classification ID

54E35: Metric spaces, metrizability

05C20: Directed graphs (digraphs), tournaments

15A03: Vector spaces, linear dependence, rank, lineability

Related Items

On ultrametric-preserving functions, Resistance distance in connected balanced digraphs, On the Gomory-Hu inequality, On spaces extremal for the Gomory-Hu inequality, Weak similarities of finite ultrametric and semimetric spaces, Combinatorial properties of ultrametrics and generalized ultrametrics, The range of ultrametrics, compactness, and separability, Ultrametric preserving functions and weak similarities of ultrametric spaces, On quasisymmetric mappings between ultrametric 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, Finite ultrametric balls, On some extremal properties of finite ultrametric spaces, From isomorphic rooted trees to isometric ultrametric spaces, Properties and morphisms of finite ultrametric spaces and their representing trees, 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

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