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     

Pathwidth of cubic graphs and exact algorithms

We prove that for any ?>0 there exists an integer n? such that the pathwidth of every cubic (or 3-regular) graph on n>n? vertices is at most (1/6+?)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three.     

Treewidth computations II. Lower bounds

For several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs.     

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.     

Diameter and Treewidth in Minor-Closed Graph Families,Revisited

Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter, which includes, e.g., planar graphs. This characterization has been used as the basis for several (approximation) algorithms on such graphs (e.g., [2] and [5]–[8]). The proof of Eppstein is complicated. In this short paper we obtain the same characterization with a simple proof. In addition, the relation between treewidth and diameter is slightly better and explicit.     

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.     

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n ³ ) time for treewidth and minimum fill-in.     

A Note on Multiflows and Treewidth

We consider multicommodity flow problems in capacitated graphs where the treewidth of the underlying graph is bounded by r. The parameter r is allowed to be a function of the input size. An instance of the problem consists of a capacitated graph and a collection of terminal pairs. Each terminal pair has a non-negative demand that is to be routed between the nodes in the pair. A class of optimization problems is obtained when the goal is to route a maximum number of the pairs in the graph subject to the capacity constraints on the edges. Depending on whether routings are fractional, integral or unsplittable, three different versions are obtained; these are commonly referred to respectively as maximum MCF, EDP (the demands are further constrained to be one) and UFP. We obtain the following results in such graphs.

基于有向图的进路搜索算法研究与设计

进路搜索是铁路车站计算机联锁系统的基本功能,其运行效率及所得目标进路的安全性对于保证行车安全意义重大。本文通过对铁路车站站场图与有向图的相似性进行研究,建立其网络拓扑结构与节点模型,结合深度优先遍历算法和搜索约束条件,提出一种适用于铁路车站实际情况的进路搜索算法,并给出了完整的描述。     

Graph searching with advice

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70–84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice   of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is Θ(nlogn)$\Theta (nlogn)$, where n$n$ is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G$G$, using a total of O(nlogn)$O(nlogn)$ bits, and a protocol using this labelling that enables the optimal number of searchers to clear G$G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires Ω(nlogn)$\Omega (nlogn)$ bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.     

Planar Graph Blocking for External Searching

Abstract. We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.     

From UML Models to Graph Transformation Systems

In this paper we present an approach that allows to validate properties of UML models. The approach is based on an integrated semantics for central parts of the UML. We formally cover UML use case, class, object, statechart, collaboration, and sequence diagrams. Additionally full OCL is supported in the common UML fashion. Our semantics is based on the translation of a UML model into a graph transformation system consisting of graph transformation rules and a working graph that represents the system state. By applying the rules on the working graph, the evolution of the modeled system is simulated.     

Treewidth Lower Bounds with Brambles

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs. This work was partially supported by the Netherlands Organisation for Scientific Research NWO (project Treewidth and Combinatorial Optimisation) and partially by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4).     

Parameterized complexity of coloring problems: Treewidth versus vertex cover

We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, L(p,1)-Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.     

图搜索中A*算法的SQL解法

讨论图搜索的Ａ＊算法和ＳＱＬ算法,利用数据库存储图中原始数据,借助ＳＱＬ语言来生成Ａ＊算法求取的解,简化了编程。     

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).     

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

We study the problem of decomposing the vertex set V$V$ of a graph into two nonempty parts _V1,_V2$V_1,V_2$ which induce subgraphs where each vertex v∈_V1$v\in V_1$ has degree at least a(v)$a(v)$ inside _V1$V_1$ and each v∈_V2$v\in V_2$ has degree at least b(v)$b(v)$ inside _V2$V_2$. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.     

数据库嵌套查询技术的应用

查询是对数据库中的记录进行选择和投影运算,得到满足条件的记录,是对数据库进行数据检索最常用的方法。如何简化查询语句的编写,提高数据查询效率是我们关心的问题,嵌套查询是解决复杂查询并实现高效查询的有效方法。