Search

Literature concerning two cultural models as potential frameworks for family counseling is reviewedfrom a Theory perspective.

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game domination number. Here we study the γg-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γg-critical graphs with γg = 2 and with γg = 3, moreover for each n we identify the (infinite) class of all γg-critical ones among the nth powers C n N of cycles. Along the way we determine γg(C n N) for all n and N. Results of a computer search for γg-critical trees are presented and several problems and research directions are also listed.

Two O(log/sup 2/ n) time algorithms are proposed for computing the dominators and constructing the dominator tree of a directed acyclic graph, G=(V, E), |V|=n, |E|=m. The parallel computation used is a practical SIMD hypercube multiprocessor with n/sup 3/ processing elements. The algorithms developed in this paper achieve the same time complexity as those developed on PRAM model (S. Pawagi, 1987), (C. Savage, 1977) but are more practical. >

Presents an efficient improvement of processor complexity while solving some connectivity problems in processor arrays with reconfigurable bus systems. We first derive two constant time algorithms in the proposed parallel processing system for computing the dominators and the dominator tree of an undirected graph either using a 9-D n/spl times/n/spl times/n processors or a 2-D n/sup 2//spl times/n/sup 2/ processors, where n is the number of vertices of the graph. Then based on the dominator tree algorithm, we also solve many other graph connectivity problems in constant time. They are the articulation points, bridges, biconnected components, and bridge-connected components problems in undirected graphs.

Exact direction and distance vectors are essential for detecting hierarchical parallelism and examining legality of loop transformation for a multiple level loop nest. Much of this work has been concentrated on array references. Little has been done to address the problems of finding precise dependences between scalar references, except to use extended SSA form with factored use-def links. In this paper, we present a technique for calculating precise direction and distance vectors for scalar references within nested loops without using any forms of SSA. To do this, we use conventional use-def links in combination with joint dominator and joint postdominator relationships, which are extended from dominator and postdominator respectively in standard data flow analysis. The precision of dependence information gathered by our algorithm can not be achieved by traditional analysis of dominator or reaching definitions.

Due to the reconvergent fanouts which make the dependency among objectives and block the fault propagation, there may exist redundant faults in the circuits. This paper presents the isomorphism identification algorithm and the pseudo dominator algorithm which are used to identify redundant faults. Experimental results on ISCAS 85 benchmark circuits show that these algorithms are efficient in identifying redundant faults.

A procedure for identifying functionally equivalent faults and improving the performance of diagnostic test pattern generation is described in this paper. The procedure is based on evaluation of faulty functions in cones of dominator gates of fault pairs. This is enhanced by utilizing circuit redundancy information. Equivalence is proved without the previously required circuit transformations. Stem-branch equivalences for reconvergent stems and their branches are identified efficiently obviating the need to check for non-masking and multiple-path sensitization. Both static and dynamic techniques are developed to exploit relations among inputs of dominator cones. This reduces the simulation time required by the procedure and enables evaluation of larger cones than could be evaluated earlier. As a result, more equivalent fault pairs are identified. Experiments performed on ISCAS85 circuits and full scan ISCAS89 circuits are used to demonstrate the effectiveness of the proposed techniques.

We consider the following decision problems. PROOFNET: given a multiplicative linear logic (MLL) proof structure, is it a proof net? ESSNET: given an essential net (of an intuitionistic MLL sequent), is it correct? The authors show that linear-time algorithms for ESSNET can be obtained by constructing the dominator tree of the input essential net. As a corollary, by showing that PROOFNET is linear-time reducible to ESSNET (by the trip translation), we obtain a linear-time algorithm for PROOFNET. We show further that these linear-time algorithms can be optimized to simple one-pass algorithms: each node of the input structure is visited at most once. As another application of dominator trees, we obtain linear time algorithms for sequentializing proof nets (i.e. given a proof net, find a derivation for the underlying MLL sequent) and essential nets.

In this paper, we present a competent algorithm to the alternative wiring problem by exploring the relationship between dominators of a target wire. Alternative wiring refers to the process of adding a redundant connection to a circuit such that a target connection will become redundant and can be removed from the circuit without altering the functionality of the circuit. The well-known ATPG-based alternative wiring scheme, redundancy addition and removal for multi-level Boolean optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. The deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires in the circuit. Implication-tree based alternative wiring logic transformation algorithm (IBAW) improves the speed of RAMBO by introducing an implication-tree structure for source node identification. Our approach of investigating the dominator relationship suggests that a large subset of unnecessary redundancy checks can be further avoided in order to improve the efficiency. Experiments were performed on MCNC benchmark circuits and results are compared to those of RAMBO and IBAW. Results show that our proposed algorithm improves IBAW with a 2.3 times speedup. Moreover, our implementation runs 8.8 times faster than RAMBO while solution quality is still maintained.

Containment of objects is a natural concept that has been poorly supported in object-oriented programming languages. For a predefined set of ownership contexts, this paper presents a type system that enforces certain containment relationships for run-time objects. A fixed ordering relationship is presumed between the owners.The formalisation of ownership types has developed from our work with flexible alias protection together with an investigation of structural properties of object graphs based on dominator trees. Our general ownership type system permits fresh ownership contexts to be created at run-time. Here we present a simplified system in which the ownership contexts are predefined. This is powerful enough to express and enforce constraints about a system's high-level structure.Our formal system is presented in an imperative variant of the object calculus. We present type preservation and soundness results. Furthermore we highlight how these type theoretic results establish a containment invariant for objects, in which access to contained objects is only permitted via their owners. In effect, the predefined ownership ordering restricts the permissible inter-object reference structure.

This article explores the concept of loops and loop nesting forests of control-flow graphs, using the problem of constructing the dominator tree of a graph and the problem of computing the iterated dominance frontier of a set of vertices in a graph as guiding applications. The contributions of this article include: (1) An axiomatic characterization, as well as a constructive characterization, of a family of loop nesting forests that includes various specific loop nesting forests that have been previously defined. (2) The definition of a new loop nesting forest, as well as an efficient, almost linear-time, algorithm for constructing this forest. (3) An illustration of how loop nesting forests can be used to transform arbitrary (potentially irreducible) problem instances into equivalent acylic graph problem instances in the case of the two problems of (a) constructing the dominator tree of a graph, and (b) computing the iterated dominance frontier of a set of vertices in a graph, leading to new, almost linear-time, algorithms for these problems.

Coverage testing techniques, such as statement and decision coverage, play a significant role in improving the quality of software systems. Constructing a thorough set of tests that yield high coverage, however, is often a very tedious, time consuming task. In this paper we present a technique to find a small subset of a program's statements and decisions with the property that covering the subset implies covering the rest. We introduce the notion of a mega block which is a set of basic blocks spanning multiple procedures with the property that one basic block in it is executed iff every basic block in it is executed. We also present an algorithm to construct a data structure called the global dominator graph showing dominator relationships among mega blocks. A tester only needs to create test cases that are aimed at executing one basic block from each of the leaf nodes in this directed acyclic graph. Every other basic block in the program will automatically be covered by the same test set.

In this paper we propose a uniform approach to deal with incremental problems on digraphs and with decremental problems on dags generalizing a technique used by La Poutre and van Leeuwen in [17] for updating the transitive closure and the transitive reduction of a dag. We define a propagation property on a binary relationship over the vertices of a digraph as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems by simply setting appropriate boundary conditions. In particular, we provide semi-dynamic algorithms and data structures for maintaining a binary relationship over the vertices of a digraph (dag) with n vertices and m edges, requiring O(n max {q, m}) total time for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Ω(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n2). We apply the proposed technique to various problems about dominance, providing a solution to the problems of maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a digraph in the incremental case, and of a dag in the decremental case; no dynamic solution was previously known for some of these problems. Finally we mention that the algorithms indeed work correctly also for interleaved sequences of insertion and deletion of edges in a dag, although the complexity bound holds for monotone sequence of updates only.

In this paper we generalize a technique used by La Poutre and van Leeuwen in [14] for updating the transitive closure and the transitive reduction of a dag, and propose a uniform approach to deal with semi-dynamic problems on dags. We define a propagation property on a binary relationship as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems on dags by simply setting appropriate border conditions.

Data flow analysis based on an incremental approach may require that the dominator tree be correctly maintained at all times. Previous solutions to the problem of incrementally maintaining dominator trees were restricted to reducible flowgraphs. In this paper we present a new algorithm for incrementally maintaining the dominator tree of an arbitrary flowgraph, either reducible or irreducible, based on a program representation called the DJ-graph. For the case where an edge is inserted, our algorithm is also faster than previous approaches (in the worst case). For the deletion case, our algorithm is likely to run fast on the average cases.

Precise value-based data dependence analysis for scalars is useful for advanced compiler optimizations. The new method presented here for flow and output dependence uses Factored Use and Def chains (FUD chains), our interpretation and extension of Static Single Assignment. It is precise with respect to conditional control flow and dependence vectors. Our method detects dependences which are independent with respect to arbitrary loop nesting, as well as loop-carried dependences. A loop-carried dependence is further classified as being carried by the previous iteration, with distance 1, or by any previous iteration, with direction

Dataflow analysis framework based on Static Single Assignment (SSA) form and Sparse Evaluation Graphs (SEGs) demand fast computation of program points where data flow information must be merged, the so-called φ-nodes. In this paper, we present a surprisingly simple algorithm for computing φ-nodes for arbitrary flowgraphs (reducible or irreducible) that runs in linear time. We employ a novel program representation—the DJ graph—by augmenting the dominator tree of a flowgraph with edges which may lead to a potential “merge” of dataflow information. In searching for φ-nodes we never visit an edge in the DJ-graph more than once by guiding the search of nodes by their levels in the dominator tree.The algorithm has been implemented and the results are compared with the well known algorithm due to Cytron et al. A consistent and significant speedup has been observed over a range of 46 Fortran procedures taken from a number of benchmark programs. We also ran experiments on increasingly taller ladder graphs and confirmed the linear time complexity of our algorithm.

In this paper Quasi-complemented lattices are characterized in terms of dominator ideals. A closure operator is introduced on the ideal lattice and with the help of this operator the concept of closure ideals is introduced and then these ideals are characterized. Further, a one-to-one correspondence between the class of all prime closure ideals of a lattice and the ideal lattice of the lattice of all dominator ideals is established.

In this paper we present techniques to find subsets of nodes of a flowgraph that satisfy the following property: A test set that exercises all nodes in a subset exercises all nodes in the flowgraph. Analogous techniques to find subsets of edges are also proposed. These techniques may be used to significantly reduce the cost of coverage testing of programs. A notion of a super block consisting of one or more basic blocks in that super block must be exercised by the same input. Dominator relationships among super blocks are used to identify a subset of the super blocks whose coverage implies that of all super blocks and, in turn, that of all basic blocks. Experiments with eight systems in the range of 1-75K lines of code show that, on the average, test cases targeted to cover just 29% of the basic blocks and 32% of the branches ensure 100% block and branch coverage, respectively.

We present a new incremental algorithm for the problem of maintaining the dominator tree of a reducible flowgraph as the flowgraph undergoes changes such as the insertion and deletion of edges. Such an algorithm has applications in incremental dataflow analysis and incremental compilation.

DS Dominator, a green cotyledon field pea (Pisum sativum L.) cultivar, was released in 2000 by Agriprogress Inc., Morden, Manitoba. DS Dominator has a semileafless leaf type, powdery mildew resistance, good lodging resistance, medium sized, round seeds, and good yielding ability. DS Dominator is adapted to the field pea-growing region of western Canada. Key words: Field pea, Pisum sativum L., cultivar description, powdery mildew resistance

We describe and prove algorithms to convert programs which use the Parallel Computing Forum Parallel Sections construct into Static Single Assignment (SSA) form. This proces allows compilers to apply classical scalar optimization algorithms to explicitly parallel programs. To do so, we must define what the concept of dominator and dominance frontier mean in parallel programs. We also describe how we extend SSA form to handle parallel updates and still preserve the SSA properties.

We present a new technique for constructing a program dependence graph that contains a program's control flow, along with the usual control and data dependence information. Our algorithm constructs a program dependence graph while the program is being parsed. For programs containing only structured transfers of control, our algorithm does not require information provided by the control flow graph or post dominator tree and therefore obviates the construction of these auxiliary graphs. For programs containing explicit transfers of control, our algorithm adjusts the partial control dependence subgraph, constructed during the parse, to incorporate exact control dependence information. There are several advantages to our approach. For many programs, our algorithm may result in substantial savings in time and memory since our construction of the program dependence graph does not require the auxiliary graph. Furthermore, since we incorporate control and data flow as well as exact control dependence information into the program dependence graph, our graph has a wide range of applicability. We have implemented our algorithm by incorporating it into the Free Software Foundation's GNU C compiler; currently we are performing experiments that compare our technique with the traditional approach.

Program representation plays an important role in software engineering, because it is used by the tools supporting software life cycle activities. To represent a program's control structure, the donünator tree and the implied tree, derived from the program's ddgraph, can be profitably used. In fact, thanks to their recursive structure, these trees are especially statable for designing very simple and efficient algorithms for program path analysis, which is widely used in measurement and testing activities. In particular, this paper presents a recursive algorithm PE for computing path expressions from the dominator and the implied trees. The algorithm proposed is of interest to program comprehension for two reasons: representation of programs by path expressions is widely applied, e.g., to testing, data flow analysis and development of complexity metrics. More in general, an algorithm as PE, which computes path expressions from flowgraphs, can be used to solve many lands of path problems.

The notion of dominators is generalized to include multiple-vertex dominators in addition to single-vertex dominators. A multiple-vertex dominator of a vertex is a group of vertices that collectively dominate the vertex. Existing algorithms compute immediate single-vertex dominators, and an algorithm for computing immediate multiple-vertex dominators is presented in this paper. The immediate dominator information is expressed in the form of a directed acyclic graph referred to as the dominator DAG or the DDAG. The generalized dominator set of any vertex dominators of the vertex, can be computed from the DDAG. The single-vertex dominator information restricts the propagation of loop invariant statements and array bound checks out of loops. Generalized dominator information avoids these restrictions. In addition, it can be used to identify natural loops and improve the existing optimization algorithm for code hoisting. The dual notion of generalized post-dominators can be used for computing control dependences and automatic generation of compact test suites for programs.

Existing algorithms for computing dominators are formulated for control flow graphs of single procedures. With the rise of computing power, and the viability of whole-program analyses and optimizations, there is a growing need to extend the dominator computation algorithms to context-sensitive interprocedural dominators. Because the transitive reduction of the interprocedural dominator graph is not a tree, as in the intraprocedural case, it is not possible to extend existing algorithms directly. In this article, we propose a new algorithm for computing interprocedural dominators. Although the theoretical complexity of this new algorithm is as high as that of a straightforward iterative solution of the data flow equations, our experimental evaluation demonstrates that the algorithm is practically viable, even for programs consisting of several hundred thousands of basic blocks.

An algorithm for computing bound sets of a Boolean function on its circuit representation is presented. The identification of bound sets is useful for many applications in logic synthesis, formal verification and testing. The presented algorithm computes bound sets by analysing dominator relations of the circuit. It has O(e·log n) worst-case complexity, where e is the number of edges and n is the number of vertices of the circuit graph. The experimental results show that the algorithm is efficient for large functions and allows computing bound sets for cases that were not possible to handle with previous methods.

Software group productivity can be dominated by many factors. A dominator is a single factor that causes productivity to decline ten-fold. The software productivity dominators discussed are design partition and communications. A model is developed to show the effect of intra-group communications on software group productivity, efficiency and group productivity speed up.

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of $O(V\log V + E)$ if V is the number of vertices and E is the number of edges in the graph. This bound compares favorably with the $O(V(V + E))$ time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the $O(V + E\log E)$ time bound of a known algorithm for finding dominators in reducible graphs. If $E \geqq V\log V$, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.

A simple, iterative bit propagation algorithm for solving global data flow analysis problems such as “available expressions” and “live variables” is presented and shown to be quite comparable in speed to the corresponding interval analysis algorithm. This comparison is facilitated by a result relating two parameters of a reducible flow graph (rfg). Namely, if G is an rfg, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then $k \geqq d$. (Intuitively, k is the maximum nesting depth of loops in a computer program, while d is a measure of the maximum loop-interconnectedness.) The node ordering employed by the simple algorithm is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of the flow graph. In addition, a dominator algorithm for an rfg is presented which takes O(edges) bit vector steps.

The analytical Framework of the social relation which is based by the interests is proposed in this paper.The theoretical construction is a following. The structure of domination is one dimension of social structure. It consists of a dominator, relation of domination, and process of domination. The core of relation of domination is a power, that is to say, exercise of power resources. The power is classified four types, and these form the foundation of hierarchical domination.We use the intermediate concept to analyze the relation of domination. It is named the “decision”, which is the key concept to declare a phenomenon of domination. The nature of domination differs either the existing the decision area or not.The relation of domination does not exist independently, but is situated the network of many factors. We say it the situation of domination. The two pattern of domination that considered the situation of domination is derived. Those are the Dependence-power relation and the Delegation-power relation, which consist of one part of the structure of domination.

We present a fast parallel algorithm for computing the dominators of a directed acyclic graph. The model of computation used in a parallel random access machine that allows simultaneous reads but prohibits simultaneous writes into the same memory location. Let P t (n) be the processor complexity of computing the transitive closure of an n-vertex directed graph on this model. The only known parallel algorithm for dominators requires O(log 2 n) time and uses O(nP t (n)) processors. Our algorithm for dominators has the same time complexity but uses O(P t (n)) processors, thereby improving the processor complexity of the previously known algorithm by a factor of n.

In an MOS transistor network information can propagate through transistors and connections in both directions. Sometimes, however, it is intended to propagate in one direction only. Propagation in the wrong direction, causing a so called sneak path, could result in a functional error. We present an almost linear algorithm for detecting such sneak paths. Only consistent sneak paths, i.e., only paths that can possibly conduct, can cause a functional error; therefore, the algorithm allows inconsistent sneak paths to be left in the network. It does so without actually examining any paths, which would be too inefficient.

Green found the closed‐form formulas for the element values in a resistance‐terminated ladder network that has a maximally flat (Butterworth) or equal‐ripple (Tschebyscheff) characteristic. The Green formulas apply only when all the zeros of the reflection coefficient ρ are chosen to lie in one half‐plane. In this paper we present new formulas for the element values for the case in which the zeros of ρ are chosen to alternate in the left and right half‐planes. These formulas apply for n odd, where n is the degree of the dominator of the transfer function, and for any nonzero ratio of the output to the input resistance. The networks obtained are related to the symmetrical ones given by Bennett's and Belevitch's formulas for matched networks.

In this paper, defining link reliability strategy constructed by remain energy, and communication cost of nodes as topology weight to synthetically reflect the energy efficiency of dominator, an Energy-radio and communication cost route (ECCR) is proposed to solve the problem that the average energy consumption in cluster and minimum communication cost. We take node residual energy and distance between sink and node to compete cluster head, at the same time, in order to reduce the cluster head energy costs, link reliability and hop is used to establish topology. The experimental results show that the algorithm not only has the energy saved characters, but also ensures the reliability of topology links and extends the network life-cycle efficiently.

IN 1943 I gave a summary1 in Nature of my analysis of the retinal colour receptors isolated with micro-electrodes on the optic nerve reached from the inside of the opened bulbs of various light-adapted animals, anaesthetized or decerebrated. Two types of responses were found to be represented by single fibres: narrow bands of sensitivity located in three preferential regions of the spectrum, 0·600–0·580 µ (red-yellow), 0·500–0·540 µ (green) and 0·460 µ (blue). These were called modulators. In addition, there was a broad band, called the dominator, with maximum at 0·560 µ, and a distribution of sensitivity corresponding to the human photopic luminosity curve. The dominator was held to mediate the sensation of white. The modulators were located by a 'chance method' of surveying a large number of light-adapted retinae. It seemed desirable to check these results by devising a method for removing this element of chance, and at the same time to find out whether the dominator could be regarded as the sum of a number of modulators. To this end a method of selective adaptation was employed. The new results obtained will now be briefly summarized. They represent my general solution of the problem and have confirmed and extended the earlier results.

We present an algorithm for updating data flow information derived from a program, in response to program edits. Our algorithm, applicable to intraprocedural or interprocedural data flow problems, is more general than previous methods because it can update any monotone data flow problem defined on a reducible flow graph and can handle arbitrary program edits.Rather than design yet another special-purpose data flow update algorithm, we show how to reduce the class of data flow problems to another class of problems which already has a fast update algorithm. More specifically, we reduce a monotone data flow problem formulated for solution using Graham-Wegman elimination [12] to the problem of constructing and decorating an attributed tree structurally isomorphic to the dominator tree of the program flow graph.To update this dominator tree in response to program changes, we first show how to express domination in terms of two local properties of nodes and edges in the flow graph — niceness and deepness. Domination is then updated in response to an edge addition or deletion by repeatedly performing two local operations on the dominator tree, each operation restoring the local properties violated by the edge change. Second, we extend Reps' attributed tree update techniques [19,21,20] and his complexity analysis, to update attribute values in response to changes in this structure.

Fast parallel algorithms are presented for updating the transitive closure, the dominator tree, and a topological ordering of a directed acyclic graph (DAG) when an incremental change has been made to it. The kinds of changes that are considered here include insertion of a vertex or insertion and deletion of an edge. The machine model used is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper require O(log n) time and use (O cu n) processors. These algorithms are efficient when compared to previously known O(log sq n) time algorithms for initial computation of the above mentioned properties of DAGs. The authors describe a new algorithm for initial computation of the dominator tree of a DAG. Their algorithm improves the processor complexity of a previously known algorithm by a factor of n, but does not affect the time complexity, which remains O(log sq n). (Author)

Summary. Single spikes have been recorded by the micro-electrode technique from the retina of the fully dark adapted decerebrate cat, the aim being to determine the curve of the scotopic dominator with a maximum degree of accuracy in order to find out whether it corresponds with the visual purple (V. P.) distribution of sensitivity as known from work on retinal extracts. The pure on-elements and some of the on/off-elements gave a curve slightly narrower than the V. P. curve (e. g. figs. 1 and 2). Some on/off-elements behaved differently. There were humps in the long and short wave-lengths in the regions where previously modulators have been noted. In some elements unexpectedly large values were obtained at 0.420 μ (e. g. figs. 3–6). It is concluded that, since the V. P. chromophore would be a complex structure with several conjugated double bonds, it may exist in the retina in states of different probability depending upon the free radicals and the receptor proteins.

Code reuse and copying is a widespread practice in software development. Detecting code clones, i.e., identical or similar fragments of code, is thus an important task with many applications, ranging from code search to bug finding and malware detection. In this paper, we propose a new approach to detect code clones in source code. Instead of analyzing the code tokens or syntax, our technique is based upon control flow analysis and dominator trees. In this way, the technique not only detects exact and syntactically similar near-miss code clones but also two new types of clones, which we characterize as structural code clones and subclones. For implementation and evaluation, we have developed the tool StoneDetector, which finds code clones in Java source code. StoneDetector performs competitive with the state of the art as measured on the BigCloneBench benchmark and finds more structural clones and subclones.

Recently it has been discovered that control flow graphs of structured programs (\equiv goto-free) have bounded treewidth t . Moreover, a bounded tree decomposition can be obtained directly from the parsing of the program [23]. In this paper we show that this knowledge can be used to design a fast algorithms for the generalized dominator problem from control flow analysis: given a digraph G=(V,E) with a start node s∈ V , for every v∈ V find the set of predecessors of v that can be reached from s without passing any other predecessors of v . We give an O(|V|t 4 ) algorithm for this problem. The problem was originally proposed by Gupta [12]. Without the restriction to bounded treewidth the fastest algorithm runs in O(|V|*|E|) and is due to Alstrup et al. [2].

EgeUn###, A critical node (cut vertex or articulation point) in wireless sensor networks, is a node which its failure breaks the connectivity of the network. Therefore, it is crucial that critical nodes be detected and treated with caution. This paper provides two localized distributed algorithms for determining the states of nodes (critical or noncritical). The first proposed algorithm identifies most of the critical and noncritical dominator nodes from two-hop local subgraph and connected dominating set (CDS) information that limits the computational complexity to O(Delta(2)) and bit complexity to O(clog(2) n) where Delta is the maximum node degree, c is the critical node count, and n is the node count. The testbed experiments and simulation results show that this algorithm detects up to 93% of critical nodes and achieves up to 91% of state determination with low energy consumption. The second proposed algorithm, which is based on the first one, finds the states of all nodes by running a limited distributed depth-first search algorithm in unrecognized parts of the network without traversing the whole network. Comprehensive testbed experiments and simulation results reveal that, in the presence of a CDS, this algorithm finds all critical nodes with lower energy consumption than all existing algorithms., TUBITAK (Scientific and Technical Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [113E470], This work was supported by TUBITAK (Scientific and Technical Research Council of Turkey) under grant 113E470.

In the domination game, introduced by Bre\v{s}ar, Klav\v{z}ar and Rall in 2010, Dominator and Staller alternately select a vertex of a graph $G$. A move is legal if the selected vertex $v$ dominates at least one new vertex -- that is, if we have a $u\in N[v]$ for which no vertex from $N[u]$ was chosen up to this point of the game. The game ends when no more legal moves can be made, and its length equals the number of vertices selected. The goal of Dominator is to minimize whilst that of Staller is to maximize the length of the game. The game domination number $\gamma_g(G)$ of $G$ is the length of the domination game in which Dominator starts and both players play optimally. In this paper we establish an upper bound on $\gamma_g(G)$ in terms of the minimum degree $\delta$ and the order $n$ of $G$. Our main result states that for every $\delta \ge 4$, $$\gamma_g(G)\le \frac{30\delta^4-56\delta^3-258\delta^2+708\delta-432}{90\delta^4-390\delta^3+348\delta^2+348\delta-432}\; n.$$ Particularly, $\gamma_g(G) < 0.5139\; n$ holds for every graph of minimum degree 4, and $\gamma_g(G)< 0.4803\; n$ if the minimum degree is greater than 4. Additionally, we prove that $\gamma_g(G) < 0.5574\; n$ if $\delta=3$., Comment: 20 pages