Monotonicity of non-deterministic graph searching

In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack.

Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS’05, 2005, pp. 364–375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open.

In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.     

Connected searching of weighted trees

In this paper we consider the problem of connected edge searching of weighted trees. Barrière et al. claim in [L. Barrière, P. Flocchini, P. Fraigniaud, N. Santoro, Capture of an intruder by mobile agents, in: SPAA’02: Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, NY, USA, 2002, pp. 200-209] that there exists a polynomial-time algorithm for finding an optimal search strategy, that is, a strategy that minimizes the number of used searchers. However, due to some flaws in their algorithm, the problem turns out to be open. It is proven in this paper that the considered problem is strongly NP-complete even for node-weighted trees (the weight of each edge is 1) with one vertex of degree greater than 2. It is also shown that there exists a polynomial-time algorithm for finding an optimal connected search strategy for a given bounded degree tree with arbitrary weights on the edges and on the vertices. This is an FPT algorithm with respect to the maximum degree of a tree.     

Digraph decompositions and monotonicity in digraph searching

Graph decompositions such as tree-decompositions and associated width measures have been the focus of much attention in structural and algorithmic graph theory. In particular, it has been found that many otherwise intractable problems become tractable on graph classes of bounded tree-width.More recently, proposals have been made to define a similar notion to tree-width for directed graphs. Several proposals have appeared so far, supported by algorithmic applications.In this paper we explore the limits of algorithmic applicability of digraph decompositions and show that various natural candidates for problems, which potentially could benefit from digraphs having small “directed width”, remain NP-complete even on almost acyclic graphs.Closely related to graph and digraph decompositions are graph searching games. An important property of graph searching games is monotonicity and a large number of papers addresses the question whether particular variants of these games are monotone. However, so far for two natural types of graph searching games-underlying DAG- and Kelly-decompositions-the question whether they are monotone was still open.We settle this issue by showing that both variants, the visible and the inert invisible graph searching games on directed graphs, are non-monotone.     

Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

Nondeterministic Graph Searching: From Pathwidth to Treewidth

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. Additional support of F.V. Fomin by the Research Council of Norway. Additional supports of P. Fraigniaud from the INRIA Project “Grand Large”, and from the Project PairAPair of the ACI “Masse de Données”. Additional supports of N. Nisse from the Project Fragile of the ACI “Sécurité & Informatique”.     

Memoryless search algorithms in a network with faulty advice

In this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I find t?” by responding with the first edge on a shortest path to t. It may happen that some nodes, called liars, give bad advice. We investigate a simple memoryless algorithm which follows the advice with some fixed probability q>1/2 and otherwise chooses a random edge. If the degree of each node and number of liars k are bounded, we show that the expected number of edges traversed by the agent before finding t is bounded from above by O(d+r^k), where d is the distance between the initial and target nodes and . We also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph and the torus.     

An annotated bibliography on guaranteed graph searching

Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field.     

Improved string searching

We show that it is possible to improve the average time of the Boyer-Moore string matching algorithm using more space. This is accomplished by applying a transformation that virtually increases the size of the alphabet in use. The improvement is such that for long patterns it is possible to obtain an algorithm more than 50 per cent faster than the original one. We include experimental results on random and English text. Some improvements for searching on English text are also discussed.     

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

The bandwidth minimization problem has a long history and a number of practical applications. In this paper we introduce a natural extension of bandwidth to partially ordered layouts. We consider this extension from three main viewpoints: graph searching, tree decompositions, and elimination orderings. The three graph parameters pathwidth, profile, and bandwidth related to linear layouts can be defined by variants of graph searching using a standard fugitive. Switching to an inert fugitive, the two former parameters are extended to treewidth and fill-in, and our first viewpoint considers the analogous tree-like extension that arises from the bandwidth variant. Bandwidth also has a definition in terms of ordered path decompositions, and our second viewpoint extends this in a natural way to ordered tree decompositions. In showing that both extensions are equivalent we employ the third viewpoint of elimination trees, as used in the field of sparse matrix computations. We call the resulting parameter the treespan of a graph and prove some of its combinatorial and algorithmic properties.     

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

The bandwidth minimization problem has a long history and a number of practical applications. In this paper we introduce a natural extension of bandwidth to partially ordered layouts. We consider this extension from three main viewpoints: graph searching, tree decompositions, and elimination orderings. The three graph parameters pathwidth, profile, and bandwidth related to linear layouts can be defined by variants of graph searching using a standard fugitive. Switching to an inert fugitive, the two former parameters are extended to treewidth and fill-in, and our first viewpoint considers the analogous tree-like extension that arises from the bandwidth variant. Bandwidth also has a definition in terms of ordered path decompositions, and our second viewpoint extends this in a natural way to ordered tree decompositions. In showing that both extensions are equivalent we employ the third viewpoint of elimination trees, as used in the field of sparse matrix computations. We call the resulting parameter the treespan of a graph and prove some of its combinatorial and algorithmic properties.     

Drawing maps with advice

We study the problem of the amount of information required to draw a complete or a partial map of a graph with unlabeled nodes and arbitrarily labeled ports. A mobile agent, starting at any node of an unknown connected graph and walking in it, has to accomplish one of the following tasks: draw a complete map of the graph, i.e., find an isomorphic copy of it including port numbering, or draw a partial map, i.e., a spanning tree, again with port numbering. The agent executes a deterministic algorithm and cannot mark visited nodes in any way. None of these map drawing tasks is feasible without any additional information, unless the graph is a tree. Hence we investigate the minimum number of bits of information (minimum size of advice  ) that has to be given to the agent to complete these tasks. It turns out that this minimum size of advice depends on the number n$n$ of nodes or the number m$m$ of edges of the graph, and on a crucial parameter μ$\mu$, called the multiplicity of the graph, which measures the number of nodes that have an identical view of the graph.     

Time constrained graph searching

We consider time constraints for four models of searching graphs for intruders. One model is the standard cops and robber vertex-searching model with complete visibility. The second model differs from the preceding one only in that none of the searchers can see the intruder. The third model is a vertex-searching model in which searchers and an intruder move simultaneously and none of the searchers can see the intruder. The fourth model is simultaneous edge searching with an arbitrarily fast intruder.     

Planning procedural advice

A planner which generates advice about the procedures which should be carried out by a human agent in order to achieve a goal is described. The fact that the agent is a person, not a robot, makes it possible to develop plans cooperatively with the user in the course of a dialogue, but imposes special requirements on the planner. The planner should be capable of taking advantage of the user's knowledge and abilities; of providing partial plans; of planning even in the absence of complete knowledge about the user's current state; of re-planning when the execution does not succeed or the situation changes; and of providing explanations of its advice. The paper considers the implications of these requirements on the design of such an advisory planner, implemented as part of the ‘Advice System’, a knowledge-based system for advising members of the public about welfare benefits.     

Tuning the boyer-moore-horspool string searching algorithm

Substring search is a common activity in computing. The fastest known search method is that of Boyer and Moore with the improvements introduced by Horspool. This paper presents a new implementation which takes advantage of the dependencies between the characters. The resulting code runs 25 per cent faster than the best currently-known routine.     

Fast string searching

Since the Boyer-Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer-Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.     

化学结构绘制软件Chemsketch3.5

此软件是加拿大ＡｄｖａｎｃｅｄＣｈｅｍｉｓｔｒｙＤｅｖｅｌｏｐｍｅｎｔＩｎｃ.(ＡＣＤ)公司的产品 ,它是ＡＣＤ公司为其ＮＭＲ谱图数据库以及物性估算软件设计的化学结构输入软件 ,Ｃｈｅｍｓｋｅｔｃｈ 3 5是目前能运行于ＰＣ机、用来绘制化学结构的功能较强的软件 ,另外 ,软件附加的化学 3Ｄ结构显示程序 ,可对其绘制的 2Ｄ化学结构进行结构优化 ,进而显示 3Ｄ结构 ,并且可进行全方位的转动 ,我们可以从不同角度观察化学结构。这个软件不仅可以帮助化学工作者绘制化学结构图用于化学论文 ,甚至可以作为科学研究的辅助工具 ,而且也可…     

论计算机搜查中的隐私权保护

本文对计算机所包含的内容的特点进行分析,进而说明实际计算机搜查中启动条件的随意性、搜查对象的不确定性和司法审查的欠缺性,为计算机搜查的研究提出一些问题。     

Edge and node searching problems on trees

In this paper, we consider the edge searching and node searching problems on trees. Given a tree, we show a transformation from an optimal node-search strategy to an optimal edge-search strategy. Using our transformation, we simplify a previous linear-time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an optimal edge-search strategy of an n-vertex tree from O(nlogn) to O(n). We also improve the running time of a previous algorithm for constructing an optimal min-cut linear layout of an n-vertex tree with the maximum degree 3 from O(nlogn) to O(n).     

Improved second-order bounds for prediction with expert advice

This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting strategy and the payoff of the best action. In this setting, we derive new and sharper regret bounds for the well-known exponentially weighted average forecaster and for a second forecaster with a different multiplicative update rule. Our analysis has two main advantages: first, no preliminary knowledge about the payoff sequence is needed, not even its range; second, our bounds are expressed in terms of sums of squared payoffs, replacing larger first-order quantities appearing in previous bounds. In addition, our most refined bounds have the natural and desirable property of being stable under rescalings and general translations of the payoff sequence. Editor: Avrim Blum An extended abstract appeared in the Proceedings of the 18th Annual Conference on Learning Theory, Springer, 2005. The work of all authors was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. The work was done while Yishay Mansour was a fellow in the Institute of Advance studies, Hebrew University. His work was also supported by a grant no. 1079/04 from the Israel Science Foundation and an IBM faculty award.