Graphs with \(G^p\)-connected medians

DOI10.1007/s10107-023-01939-3arXiv2201.12248OpenAlexW4226205068MaRDI QIDQ6120939

Yann Vaxès, Jérémie Chalopin, Laurine Bénéteau, Victor Chepoi

Publication date: 21 February 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.12248

zbMATH Keywords

majority rulelocal medianisometric subgraphs of halved-cubes with connected mediansisometric subgraphs of Johnson graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bucolic complexes
• Peakless and monotone functions on G-spaces
• Medians in median graphs
• Basis graphs of even delta-matroids
• Embedding graphs as isometric medians
• Pseudo-modular graphs
• On local convexity in graphs
• On the use of ordered sets in problems of comparison and consensus of classifications
• A Helly theorem in weakly modular space
• The median procedure in cluster analysis and social choice theory
• Discrete convex analysis
• Fiber-complemented graphs. II: Retractions and endomorphisms
• Median problem in some plane triangulations and quadrangulations.
• Decomposition and \(l_1\)-embedding of weakly median graphs
• Distance-preserving subgraphs of Johnson graphs
• Absolute retracts of bipartite graphs
• Fiber-complemented graphs. I: Structure and invariant subgraphs
• Cellular bipartite graphs
• A tight axiomatization of the median procedure on median graphs
• Medians in median graphs and their cube complexes in linear time
• The median rule in judgement aggregation
• Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
• Condorcet domains, median graphs and the single-crossing property
• On two conjectures of maurer concerning basis graphs of matroids
• The centrality index of a graph
• Matroid basis graphs. I
• Distance-preserving subgraphs of hypercubes
• Local medians in chordal graphs
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Graphs with Connected Medians
• Absolute Retracts and Varieties of Reflexive Graphs
• Retracts of hypercubes
• A Formal Theory of Consensus
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• Conditions for invariance of set diameters under d-convexification in a graph
• Medians of arbitrary graphs
• On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
• On Distance-Preserving and Domination Elimination Orderings
• Modular Interval Spaces
• Quasi‐median graphs and algebras
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• The Median Procedure in a Formal Theory of Consensus
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• A theory of measuring, electing, and ranking
• Dismantlability of weakly systolic complexes and applications
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Unimodal eccentricity in trees