Wyniki wyszukiwania dla: graph searching - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: graph searching

Wyniki wyszukiwania dla: graph searching

  • Non-monotone graph searching models

    Graph searching encompasses a variety of different models, many of which share a property that in optimal strategies fugitive can never access once searched regions. Monotonicity, as it is called, is vital in many established results in the field however its absence significantly impedes the analysis of a given problem. This survey attempts to gather non-monotone models, that are less researched in effort of summarizing the results...

  • Distributed graph searching with a sense of direction

    In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Application of genetic algorithms in graph searching problem

    Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called...

  • Multi-agent graph searching and exploration algorithms

    Publikacja

    - Rok 2020

    A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...

    Pełny tekst do pobrania w portalu

  • Comparison of reproduction strategies in genetic algorithm approach to graph searching

    genetic algorithms (ga) are a well-known tool used to obtain approximate solutions to optimization problems. successful application of genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. in this paper we focus on applying genetic algorithms in calculating...

  • Zero-Visibility Cops and Robber Game on a Graph

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2013

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Zero-visibility cops and robber and the pathwidth of a graph

    Publikacja

    - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2015

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Three-fast-searchable graphs

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2013

    In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...

    Pełny tekst do pobrania w portalu

  • On Tradeoffs Between Width- and Fill-like Graph Parameters

    In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...

    Pełny tekst do pobrania w portalu

  • Decontaminating Arbitrary Graphs by Mobile Agents: a Survey

    Publikacja

    A team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • A Framework for Searching in Graphs in the Presence of Errors

    Publikacja

    - Rok 2019

    We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction

    Ionic liquids (ILs) provide a promising solution in many industrial applications, such as solvents, absorbents, electrolytes, catalysts, lubricants, and many others. However, due to the enormous variety of their structures, uncovering or designing those with optimal attributes requires expensive and exhaustive simulations and experiments. For these reasons, searching for an efficient theoretical tool for finding the relationship...

    Pełny tekst do pobrania w portalu

  • Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs

    Publikacja

    - Rok 2011

    In the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The complexity of bicriteria tree-depth

    Publikacja

    The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On-line Search in Two-Dimensional Environment

    We consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...

    Pełny tekst do pobrania w portalu

  • On minimum cost edge searching

    Publikacja

    We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...

    Pełny tekst do pobrania w portalu

  • Joanna Raczek dr inż.

    Wykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i Telekomunikacji,...

  • Brushing with additional cleaning restrictions

    Publikacja

    In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...

    Pełny tekst do pobrania w portalu

  • The searchlight problem for road networks

    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2015

    We consider the problem of searching for a mobile intruder hiding in a road network given as the union of two or more lines, or two or more line segments, in the plane. Some of the intersections of the road network are occupied by stationary guards equipped with a number of searchlights, each of which can emit a single ray of light in any direction along the lines (or line segments) it is on. The goal is to detect the intruder,...

    Pełny tekst do pobrania w portalu

  • The Snow Team Problem

    Publikacja

    - Rok 2017

    We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b)...

    Pełny tekst do pobrania w serwisie zewnętrznym