Computing median and antimedian sets in median graphs

DOI10.1007/s00453-008-9200-4zbMath1200.68167MaRDI QIDQ2379917

Manoj Changat, Ajitha R. Subhamathi, Kannan Balakrishnan, Boštjan Brešar, Matjaž Kovše, Sandi Klavžar

Publication date: 23 March 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dyuthi.cusat.ac.in/purl/4193

zbMATH Keywords

profile; hypercube; median; weak contraction; median graph; isometric subgraph; antimedian

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

AXIOMATIC CHARACTERIZATION OF THE ANTIMEDIAN FUNCTION ON PATHS AND HYPERCUBES, On 2-Connected Transmission Irregular Graphs, On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs, Axiomatic characterization of the median and antimedian function on a complete graph minus a matching, A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Medians in median graphs
• The median procedure in cluster analysis and social choice theory
• The retracts of Hamming graphs
• Recognizing median graphs in subquadratic time
• Recognizing graphs of acyclic cubical complexes
• The median procedure on median graphs
• Fast recognition algorithms for classes of partial cubes
• Discrete facility location and routing of obnoxious activities.
• The obnoxious center problem on weighted cactus graphs.
• The median procedure in the semilattice of orders
• Fast recognition of Fibonacci cubes
• Locating two obnoxious facilities using the weighted maximin criterion
• Graphs with Connected Medians
• Retracts of hypercubes
• Arboricity and Subgraph Listing Algorithms
• Median Graphs and Triangle-Free Graphs
• Quasi‐median graphs and algebras
• Stable networks and product graphs