11/8/2022 0 Comments Unit disk graph chromatic bound![]() ![]() Even et al., ELRS03 proved that O ( log n ) colors are always sufficient to CF-color a set of disks in the plane, and in the worst case, Ω ( log n ) colors are required. Here, the range of base stations is modeled as regions e.g., disks or other geometric objects. In the CF-coloring problem we are given a set of points (representing client locations) and a set of base stations, the objective is to assign colors (representing frequencies) to the base stations such that any client lying within the range of at least one base station is covered by the base station whose color is different from the colors of the other base stations covering the client, and the number of colors used should be as minimum as possible. Although both of the approaches, initially, begin by dividing the plane, we recognize a unique bound that exists in our need to bound the colorability and provide a novel solution in the same regard.Ī notion of conflict-free coloring (CF-coloring) was introduced by Even et al., ELRS03. Our approach, however, focuses on the specific geometric properties that arise from the dual conditionals of the problem statement. In this paper, we attempt to improve upon this impractical O ( n m 25 ) running time. Based on this, they define a directed acyclic graph such that there exists a path from source to a destination corresponding to this optimal solution. To solve the problem for any strip they show that at most a constant number of disks of an optimal solution intersect any vertical line. Their approach first partitions the plane into horizontal strips, solves the problem for every strip optimally, then returns the union of solutions of all strips. They gave a 2-approximation algorithm in O ( n m 25 ) time for the 3-CDUDC problem. The 3-CDUDC problem, to the best of our knowledge, was first studied by Biedl et al., BBL19. the k -CLSDC and k -CRRC problems), instead of points. We further generalize the problem by considering line segments and a continuous rectangular region as representing potential wireless clients (resp. In the same spirit, we generalize the 3-CDUDC to the k -CDUDC problem, where k > 0 is an integer. Typically, (Wi-Fi) networks are built with 3 independent channels BHLL10, hence the motivation for a study on the 3-CDUDC problem. In the spirit of reducing interference in broadcast and other energy-saving measures, we aim to limit or reduce the number of different frequencies(channels) assigned to each, represented by coloring. The disks representing the range (which is presumably the same for all stations) of each potential host is represented by the set D. The clients themselves are represented by a set of points P in a plane. Each wireless client is equipped with corresponding receivers. In ad-hoc mobile networks, each host(station/tower) is equipped with a Radio-Frequency (RF) transceiver to provide reliable transmission inside a circular range, represented by a disk, within some distance. Our motivation for studying the problem arises from practical applications in the frequency/channel assignment problem in wireless/cellular networks. Set P of n points, we are given a set S of n line segments, and a Rectangular Region Cover (k-CRRC) problems, in which instead of the We also extend our algorithm to solve the k-Colorable Line Segment Disk Cover (k-CLSDC) and k-Colorable We then generalize our approach to exhibit a Time, faster than the previous best algorithm, but gives a 4-approximate The recent work of Biedl et al., (2021), who proposed a 2-approximationĪlgorithm in O(m^25n) time. The previous best known result for the problem when k=3 is due to Problem and then show that the running time can be improved by a multiplicativeįactor of m^k, where a positive integer k denotes the cardinality of aĬolor-set. Weįirst propose a 4-approximation algorithm in O(m^7knlog k) time for this Number of colors used in the coloring if there exists a k-colorable cover. Χ(d)≠χ(d'), where C denotes a set containing k distinct colors.įor the k-CDUDC problem, our proposed algorithms approximate the There exists a function χ:D'→ C that assigns colors to disks inĭ' such that for any d and d' in D' if d∩ d'≠∅, then The plane, and a parameter k, the objective is to compute a set D'⊆ĭ such that every point in P is covered by at least one disk in D' and P of n points, and a set D of m unit disks (of radius=1), both lying in K-Colorable Discrete Unit Disk Cover (k-CDUDC): Given a set In this article, we consider colorable variations of the Unit Disk Cover ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |