检索结果-内蒙古大学图书馆

Complexity and Approximation for Discriminating and identifying code Problems in Geometric Setups

ALGORITHMICA 2023年第7期85卷 1850-1882页

作者： Dey, Sanjana Foucaud, Florent Nandy, Subhas C. C. Sen, Arunabha Indian Stat Inst ACM Unit Kolkata India Univ Clermont Auvergne LIMOS CNRS UMR 6158 Aubiere France Univ Bordeaux LaBRI UMR5800 CNRSBordeaux INP F-33400 Talence France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France Arizona State Univ Tempe AZ 85287 USA Natl Univ Singapore Sch Comp Singapore Singapore

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R-d. The objective is to choose a subset S*subset of S of minimum cardinality such that for each point pi E P, the subset Si*subset of S* covering pi satisfies Si*not equal 0, and each pair p(i), p(j) is an element of P, i not equal j, we have S-i* not equal S-j*. In the continuous version of the problem, the solution set S* can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case (d = 1), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case (d = 2) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 center dot O PT +1)-approximate and (64 center dot O PT + 1)-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S* of objects so that all objects of S are discriminated by their intersection with the objects of S*

关键词： Discriminating code identifying code Approximation algorithm Segment stabbing Geometric hitting set

来源：评论

学校读者我要写书评

暂无评论

The watching system as a generalization of identifying code

引用

APPLIED MATHEMATICS AND COMPUTATION 2020年 380卷 125302-125302页

作者： Ghorbani, Modjtaba Dehmer, Matthias Maimani, Hamidreza Maddah, Sheyda Roozbayani, Maryam Emmert-Streib, Frank Shahid Rajaee Teacher Training Univ Fac Sci Dept Math Tehran 16785136 Iran Swiss Distance Univ Appl Sci Dept Comp Sci Brig Switzerland UMIT Dept Biomed Comp Sci & Mechatron Hall In Tirol Austria Nankai Univ Coll Artificial Intelligence Tianjin 300071 Peoples R China Tampere Univ Predict Soc & Data Analyt Lab Korkeakoulunkatu 10 Tampere 33720 Finland Tampere Univ Inst Biosci & Med Technol Korkeakoulunkatu 10 Tampere 33720 Finland

The watching system, as a generalization of identifying code, has been defined by Auger in 2010. The identifying code has been used to wireless networks and it has been also applied to locate objects in the sensor networks. On the other hand, the graph product is employed in most of the mathematic branches such as network design to study the structure of network elements. In this paper, we give some upper bounds for the watching number of well-know product graphs. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Watching system Domination number Graph products identifying code

来源：评论

学校读者我要写书评

暂无评论

The identifying code, the Locating-dominating, the Open Locating-dominating and the Locating Total-dominating Problems Under Some Graph Operations 10th

The Identifying Code, the Locating-dominating, the Open Loca...

引用

10th Latin and American Algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Argiroffo, G. Bianchi, S. Lucarini, Y. Wagler, A. Univ Nacl Rosario Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Clermont Auvergne LIMOS UMR CNRS 6158 Clermont Ferrand France

The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such codes in special graphs. In this work we study the change of minimum such codes under three operations in graphs: adding a universal vertex, taking the generalized corona of a graph, and taking the square of a graph. We apply these operations to paths and cycles which allows us to provide minimum codes in most of the resulting graph classes.

关键词： identifying code locating-dominating set open locating-dominating set locating total-dominating set

来源：评论

学校读者我要写书评

暂无评论

On Upper and Lower Bounds of identifying code Set for Soccer Ball Graph with Application to Satellite Deployment 19

On Upper and Lower Bounds of Identifying Code Set for Soccer...

引用

20th International Conference on Distributed Computing and Networking (ICDCN)

作者： Sen, Arunabha Goliber, Victoria H. Basu, Kaustav Zhou, Chenyang Ghosh, Sumitava Arizona State Univ Tempe AZ 85281 USA

ISBN: (纸本)9781450360944

We study a monitoring problem on the surface of the earth for significant environmental, social/political and extreme events using satellites as sensors. We assume that the surface of the earth is divided into a set of regions, where a region may be a continent, a country, or a set of neighboring countries. We also assume that, the impact of a significant event spills into neighboring regions and there will be corresponding indicators of such events. Careful deployment of sensors, utilizing identifying codes, can ensure that even though the number of deployed sensors is fewer than the number of regions, it may be possible to uniquely identify the region where the event has taken place. We assume that an event is confined to a region. As Earth is almost a sphere, we use a soccer ball (a sphere) as a model. From the model, we construct a Soccer Ball Graph (SBG), and show that the SBG has at least 26 sets of identifying codes of cardinality ten, implying that there are at least 26 different ways to deploy ten satellites to monitor the Earth. Finally, we also show that the size of the minimum identifying code for the SBG is at least nine.

关键词： identifying code Upper Bound Monitoring

来源：评论

学校读者我要写书评

暂无评论

The identifying code, the Locating-dominating, the Open Locating-dominating and the Locating Total-dominating Problems Under Some Graph Operations

引用

Electronic Notes in Theoretical Computer Science 2019年 346卷 135-145页

作者： G. Argiroffo S. Bianchi Y. Lucarini A. Wagler Universidad Nacional de Rosario Rosario Argentina Universidad Nacional de Rosario Rosario Argentina CONICET University Clermont Auvergne (LIMOS UMR 6158 CNRS) Clermont-Ferrand France

关键词： identifying code locating-dominating set open locating-dominating set locating total-dominating set

来源：评论

学校读者我要写书评

暂无评论

Optimal error-detection system for identifying codes

引用

NETWORKS 2025年第1期85卷 61-75页

作者： Jean, Devin C. Seo, Suk J. Vanderbilt Univ Comp Sci Dept Nashville TN 37235 USA Middle Tennessee State Univ Comp Sci Dept Murfreesboro TN USA

Assume that a graph G$$ G $$ models a detection system for a facility with a possible "intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing detectors at a subset of vertices in G$$ G $$ to determine the location of an intruder if there is any. Many types of detection systems have been defined for different sensor capabilities;in particular, we focus on identifying codes, where each detector can determine whether there is an intruder within its closed neighborhood. In this research we explore a fault-tolerant variant of identifying codes applicable to real-world systems. Specifically, error-detecting identifying codes permit a false-negative transmission from any single detector. We investigate minimum-sized error-detecting identifying codes in several classes of graphs, including cubic graphs and infinite grids, and show that the problem of determining said minimum size in arbitrary graphs is NP-complete.

关键词： domination detection system fault-tolerant identifying code infinite grids NP-complete

来源：评论

学校读者我要写书评

暂无评论

Extremal digraphs for open neighbourhood location-domination and identifying codes

引用

DISCRETE APPLIED MATHEMATICS 2024年 347卷 62-74页

作者： Foucaud, Florent Ghareghani, Narges Sharifani, Pouyeh Univ Clermont Auvergne CNRS Clermont Auvergne INP Mines St EtienneLIMOS F-63000 Clermont Ferrand France Univ Tehran Coll Fine Arts Dept Ind Design Tehran Iran Inst Res Fundamental Sci IPM Sch Math Tehran Iran

A set S of vertices of a digraph D is called an open neighbourhood locating -dominating set if every vertex in D has an in -neighbour in S, and for every pair u, v of vertices of D, there is a vertex in S that is an in -neighbour of exactly one of u and v. The smallest size of an open neighbourhood locating -dominating set of a digraph D is denoted by gamma OL(D). We study the class of digraphs D whose only open neighbourhood locating -dominating set consists of the whole set of vertices, in other words, gamma OL(D) is equal to the order of D. We call those digraphs extremal. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. We extend previous studies from the literature for both open neighbourhood locating -dominating sets and identifying codes of both undirected and directed graphs. These results all correspond to studying open neighbourhood locating -dominating sets on special classes of digraphs. To do so, we prove general structural properties of extremal digraphs, and we describe how they can all be constructed. We then use these properties to give new proofs of several known results from the literature. We also give a recursive and constructive characterization of the extremal di -trees (digraphs whose underlying undirected graph is a tree). (c) 2023 Elsevier B.V. All rights reserved.

关键词： Locating-dominating set Directed graph identifying code

来源：评论

学校读者我要写书评

暂无评论

Density of identifying codes of hexagonal grids with finite number of rows

引用

RAIRO-OPERATIONS RESEARCH 2024年第2期58卷 1633-1651页

作者： Sampaio, Rudini M. Sobral, Gabriel A. G. Wakabayashi, Yoshiko Univ Fed Ceara UFC Dept Computacao Fortaleza CE Brazil Univ Sao Paulo Inst Matemat & Estatst Sao Paulo SP Brazil

In a graph G, a set C subset of V (G) is an identifying code if, for all vertices v in G, the sets N[v] boolean AND C are all nonempty and pairwise distinct, where N[v] denotes the closed neighbourhood of v. We focus on the minimum density of identifying codes of infinite hexagonal grids Hk with k rows, denoted by d*(Hk), and present optimal solutions for k <= 5. Using the discharging method, we also prove a lower bound in terms of maximum degree for the minimum-density identifying codes of well-behaved infinite graphs. We prove that d*(H2) = 9/20, d*(H3) = 6/13 approximate to 0.4615, d*(H4) = 7/16 = 0.4375 and d*(H5) = 11/25 = 0.44. We also prove that H2 has a unique periodic identifying code with minimum density.

关键词： identifying code hexagonal grid minimum density

来源：评论

学校读者我要写书评

暂无评论

identifying codes in line digraphs

引用

APPLIED MATHEMATICS AND COMPUTATION 2020年 383卷 125357-125357页

作者： Balbuena, C. Dalfo, C. Martinez-Barona, B. Univ Politecn Cataluna Dept Engn Civil & Ambiental Barcelona Spain Univ Lleida Dept Matemat Catalonia Spain

Given an integer l >= 1, a (1, = 3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, <= 2)-identifying code. ... 详细信息

Given an integer l >= 1, a (1, <= l)-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighborhoods within C. In this paper, we prove that every line digraph of minimum in-degree one does not admit a (1, <= l)-identifying code for l >= 3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, <= 2)-identifying code. The identifying number of a digraph D, (gamma) over right arrow D-ID(D), is the minimum size of all the identifying codes of D. We establish for digraphs without digons with both vertices of in-degree one that (gamma) over right arrow (ID) (LD) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show (gamma) over right arrow (ID)(LD) attains the equality for a digraph having a 1-factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Line digraph identifying code Dominating set Separating set 1-Factor

来源：评论

学校读者我要写书评

暂无评论

On Three Domination-based Identification Problems in Block Graphs

引用

FUNDAMENTA INFORMATICAE 2024年第3-4期191卷 197-229页

作者： Chakraborty, Dipayan Foucaud, Florent Parreau, Aline Wagler, Annegret Univ Clermont Auvergne CNRS Mines St Etienne Clermont Auvergne INP LIMOS F-63000 Clermont Ferrand France Univ Lyon Univ Lyon 2 UCBL Centrale Lyon CNRSINSA LyonLIRISUMR5205 F-69622 Villeurbanne France Univ Johannesburg Dept Math & Appl Math Auckland Pk ZA-2006 Auckland Pk South Africa

The problems of determining the minimum-sized identifying, locating-dominating and open locating-dominating codes of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set C of a graph G such that the vertices of a chosen subset of V (G) (i.e. either V (G) n C or V (G) itself) are uniquely determined by their neighborhoods in C. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or blocks) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight.

关键词： identifying code locating-dominating code open locating-dominating code block graph

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：