A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs

Wei Ding (), Ke Qiu (), Yu Zhou () and Zhou Ye ()
Additional contact information
Wei Ding: Zhejiang University of Water Resources and Electric Power
Ke Qiu: Brock University
Yu Zhou: Taiyuan University of Technology
Zhou Ye: Zhejiang Ocean University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 1, 905-920

Abstract: Abstract Let $$G = (V, E, w)$$ G = ( V , E , w ) be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and $$w: E \rightarrow \mathbb {R}^+$$ w : E → R + is a positive edge-weight function. Given $$G = (V, E, w)$$ G = ( V , E , w ) , a subset $$X \subseteq V$$ X ⊆ V of p terminals, and a subset $$F \subseteq E$$ F ⊆ E of candidate edges, the Absolute 1-Center Problem (A1CP) aims to find a point on some edge in F to minimize the distance from it to X. This paper revisits this classic and polynomial-time solvable problem from a novel perspective and finds some new and nontrivial properties of it, with the highlight of establishing the relationship between the A1CP and the saddle point of distance matrix. In this paper, we prove that an absolute 1-center is just a vertex 1-center if the all-pairs shortest paths distance matrix from the vertices covered by the candidate edges in F to X has a (global) saddle point. Furthermore, we define the local saddle point of edge and demonstrate that we can sift the candidate edge having a local saddle point. By incorporating the method of sifting edges into the framework of the well-known Kariv and Hakimi’s algorithm, we develop an $$O(m + p m^*+ n p \log p)$$ O ( m + p m ∗ + n p log p ) -time algorithm for A1CP, where $$m^*$$ m ∗ is the number of the remaining candidate edges. Specifically, it takes $$O(m^*n + n^2 \log n)$$ O ( m ∗ n + n 2 log n ) time to apply our algorithm to the classic A1CP when the distance matrix is known and $$O(m n + n^2 \log n)$$ O ( m n + n 2 log n ) time when the distance matrix is unknown, which are smaller than $$O(mn + n^2 \log n)$$ O ( m n + n 2 log n ) and $$O(mn + n^3)$$ O ( m n + n 3 ) of Kariv and Hakimi’s algorithm, respectively.

Keywords: Absolute 1-center; Saddle point; Sifting edges (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00866-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:2:d:10.1007_s10878-022-00866-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00866-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().