Open problem 1. Is there an almost linear-time algorithm for the Weighted Center problem on median graphs of bounded cube-dimension?
Statement
Open problem 1. Is there an almost linear-time algorithm for the Weighted Center problem on median graphs of bounded cube-dimension? or metric spaces the classical Center problem corresponds to the particular case of the all-one profile \pi, which has attracted considerable attention in algorithmic graph theory, and in computational geometry. Motivations. The fine-grained complexity of the Weighted Center problem on median graphs can be relevant in the study of median networks [5]: that are roughly the median closure of phylogenetic data (e.g., mitochondrial DNA of hu- man populations). Indeed, in network analysis, the inverse of the radius function is used as a centrality index to determine the relative importance of the nodes in a network. Since median networks are notoriously large, it is important to design algorithms for them that are as fast as possible. On general graphs, the Center problem requires n2−o(1) time, under plausible complexity hypotheses, even on n- vertex graphs with at most n1+o(1) edges [2]. However, it is possible to break this quadratic barrier for median graphs, due to their metric and geometric properties.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.