Search

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

Abstract: Gong et al. (2010) and Xiao et al. (2010) have proposed the notion of bijective soft set and exclusive disjunctive soft set, respectively, which is a subtype of soft set. On the basis of their work, this paper extends these notions to fuzzy environments, and formulates the concept of bijective fuzzy soft set, which can deal with more uncertain problems. Moreover, this paper proposes two parameters reduction algorithms: one (Algorithm 1) is based on bijective fuzzy soft system, and the other (Algorithm 2) takes weight of an element into consideration. Since the threshold plays an important role in these algorithms, we proposed an algorithm (Algorithm 3) to decide the optimal value of threshold specially. Afterwards, an example analysis of the two parameters reduction algorithms is given and the result shows that the two algorithms lead to the same parameters reduction of a bijective fuzzy soft system. Since Algorithm 2 considers the detail weights of elements, thus it can be used in more uncertain problems, such as time series analysis problems, than Algorithm 1. [Copyright &y& Elsevier]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . The cardinality of a minimum k -path vertex cover is called the k -path vertex cover number of a graph G , denoted by ψ k ( G ) . It is known that the minimum k -path vertex cover problem ( k -PVCP) is NP-hard for all k ≥ 2 . In this paper we consider the weighted version of a k -PVCP ( k -WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P k . This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k -WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k -path vertex cover number of a tree with time complexity O ( k ⋅ | V ( G ) | ) is presented. [ABSTRACT FROM AUTHOR]

Abstract: In this paper scheduling communications in data gathering networks is analyzed. We study collecting information by a set of sensors, each of which stores the data in its memory buffer and then passes them to a base station. The network lifetime ends as soon as the first node is out of memory. We use a divisible load model to propose a communication scheduling algorithm that maximizes the system lifetime, and hence, the total amount of gathered information. The influence of the sensor communication rates on the obtained schedules is exposed in a series of computational experiments. [Copyright &y& Elsevier]

Abstract: Let be a graph with vertex set . A moplex of is both a clique and a module whose neighborhood is a minimal separator in or empty. A moplex ordering of is an ordered partition of for some integer into moplexes which are defined in the successive transitory elimination graphs, i.e., for , is a moplex of the graph induced by and induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on defines a moplex ordering of , which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques. [Copyright &y& Elsevier]

Abstract: A graph is a square root of a graph if two vertices are adjacent in if and only if they are at distance one or two in . Computing a square root of a given graph is NP-hard, even when the input graph is restricted to be chordal. In this paper, we show that computing a square root can be done in linear time for a well-known subclass of chordal graphs, the class of trivially perfect graphs. This result is obtained by developing a structural characterization of graphs that have a split square root. We also develop linear time algorithms for determining whether a threshold graph given either by a degree sequence or by a separating structure has a square root. [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [Copyright &y& Elsevier]

Abstract: Recently, a new methodology (“synergistic sensor location”) has been introduced to efficiently determine all link flows in a road network by using only a subset of the link flow measurements. In this paper, we generalize this previous work by solving the following problem: Suppose that one is only interested in a subset of the link flows, and that certain link flows are known a priori. At a minimum, what link flows are needed to be able to uniquely determine the desired link flows? An algorithm is presented that does not require the need for path enumeration. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce an generic framework for the mining of sequences under various constraints. More precisely, we study the enumeration of all partitions of a word into multisets of subsequences. We show that using additional predicates, this generator can be used for frequent subsequences and substrings mining. We define the transition graph whose vertices are multisets of words and arcs are transitions between multisets. We show that is a directed acyclic graph and it admits a covering tree. We use to propose a generic algorithm that enumerates all multisets that satisfies a set of predicates, without redundancy. [Copyright &y& Elsevier]

Abstract: In this paper, we study the class of distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization based on a restricted number of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs. [Copyright &y& Elsevier]

Abstract: Rank reversal is a phenomenon that occurs when a decision maker, in the process of selecting an alternative from a set of choices, is confronted with new alternatives that were not thought about when the selection process was initiated. It depends on the relationship between this new alternative and the old ones under each criterion. In this paper, we study the rank reversal phenomenon in the TOPSIS method and we propose modifications in the algorithm of Hwang and Yoon in order to solve the problem. Moreover, we present a general demonstration of the proposed modifications in the algorithm, as well as a numerical example to show these modifications. [Copyright &y& Elsevier]

Abstract: A graph is called an interval graph if there exists a set of intervals corresponding to the vertex set of and two vertices are adjacent to each other if and only if the two corresponding intervals are intersecting with each other. In this paper, we apply the reliability-based backup 2-center modal proposed by Wang, Wu and Chao, in which each server may fail with a given probability, to interval graphs and present an time algorithm. [Copyright &y& Elsevier]

Abstract: Let denote an -vertex and -edge graph in which is a function mapping each vertex to a positive weight and is a function mapping each edge to a positive length . Given a positive integer , the -Center problem involves finding a set with vertices of to be the locations for building facilities. The objective is to minimize the maximum weighted distance from each vertex in – to its nearest vertex in . This paper considers a practical restriction: the induced subgraph of the selected vertices must be connected. The new variant is called the Connected -Center problem (the problem). For each fixed integer , on block graphs with exactly blocks, we first show that the problem is NP-hard when (1) , for all vertices , and , for all edges , and (2) , for all vertices , and , for all edges , respectively. Second, an -time algorithm for solving the problem on block graphs with unit vertex-weights and unit edge-lengths is proposed. Then, the algorithmic result is extended to handle the situation in which some vertices in cannot be included to form feasible solutions. The complexity of the extended algorithm is also . [Copyright &y& Elsevier]

Abstract: An important issue in qualitative spatial reasoning is the representation of relative directions. In this paper we present simple geometric rules that enable reasoning about the relative direction between oriented points. This framework, the oriented point algebra , has a scalable granularity m. We develop a simple algorithm for computing the composition tables and prove its correctness. Using a composition table, algebraic closure for a set of statements is very useful for solving spatial navigation tasks. It turns out that scalable granularity is useful in these navigation tasks. [Copyright &y& Elsevier]

Abstract: Given a graph , a defensive alliance of is a set of vertices satisfying the condition that for each , at least half of the vertices in the closed neighborhood of are in . A defensive alliance is called global if every vertex in is adjacent to at least one member of the defensive alliance . The global defensive alliance number of , denoted , is the minimum size around all the global defensive alliances of . In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete -ary trees for . We also establish upper bounds and lower bounds for and , and show that the bounds are sharp for certain . [Copyright &y& Elsevier]

Abstract: The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an time and polynomial space algorithm. [Copyright &y& Elsevier]

Abstract: In this paper an attempt is made to extend some standard results in set theory on the basis of soft set relations. Antisymmetric relation and transitive closure of a soft set relation are introduced and an analogue of Warshall’s algorithm is proposed for calculating the transitive closure of a soft set relation. Ordering on a soft set is defined and some set theoretical results based on this are proved. [Copyright &y& Elsevier]

Abstract: In this paper, an active set limited BFGS algorithm is proposed for bound constrained optimization. The global convergence will be established under some suitable conditions. Numerical results show that the given method is effective. [Copyright &y& Elsevier]

Abstract: Feature selection is viewed as an important preprocessing step for pattern recognition, machine learning and data mining. Traditional hill-climbing search approaches to feature selection have difficulties to find optimal reducts. And the current stochastic search strategies, such as GA, ACO and PSO, provide a more robust solution but at the expense of increased computational effort. It is necessary to investigate fast and effective search algorithms. Rough set theory provides a mathematical tool to discover data dependencies and reduce the number of features contained in a dataset by purely structural methods. In this paper, we define a structure called power set tree (PS-tree), which is an order tree representing the power set, and each possible reduct is mapped to a node of the tree. Then, we present a rough set approach to feature selection based on PS-tree. Two kinds of pruning rules for PS-tree are given. And two novel feature selection algorithms based on PS-tree are also given. Experiment results demonstrate that our algorithms are effective and efficient. [ABSTRACT FROM AUTHOR]

Abstract: Let γ(P m □ C n ) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P m , the path of length m, m ⩾2 and the graph C n , the cycle of length n, n ⩾3. In this paper, methods to find the domination numbers of graphs of the form P m □ C n with n ⩾3 and m =2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P 5 □ C n , n ⩾3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents algorithms for decomposing any zero-dimensional polynomial set into simple sets over an arbitrary finite field, with an associated ideal or zero decomposition. As a key ingredient of these algorithms, we generalize the squarefree decomposition approach for univariate polynomials over a finite field to that over the field product determined by a simple set. As a subprocedure of the generalized squarefree decomposition approach, a method is proposed to extract the th root of any element in the field product. Experiments with a preliminary implementation show the effectiveness of our algorithms. [Copyright &y& Elsevier]

Abstract: The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) ). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) ), however the problem for the computable Lipschitz degrees is more complex. [ABSTRACT FROM AUTHOR]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: A word is a fixed point of a nontrivial morphism if and is not the identity on the alphabet of . The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters. [Copyright &y& Elsevier]

Abstract: This paper revisits the ‘branchwidth territories’ of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called -troikas: three sets of size at most each are a -troika of set , if any two have union . We give a straightforward algorithm, computing branchwidth for an interval graph on edges, vertices and maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new method for fuzzy risk analysis based on similarity measures between interval-valued fuzzy numbers. First, we present a new similarity measure between interval-valued fuzzy numbers. It combines the concepts of geometric distance, the perimeter, the height and the center-of-gravity-points of interval-valued fuzzy numbers for calculating the degree of similarity between interval-valued fuzzy numbers. We also prove some properties of the proposed similarity measure. We make an experiment to use nine sets of interval-valued fuzzy numbers to compare the experimental results of the proposed method with the existing similarity measures. The proposed method can overcome the drawbacks of the existing similarity measures. We also propose a new division operator and an interval-valued fuzzy number adjustment algorithm. Based on the proposed similarity measure, new division operator and adjustment algorithm, we present a new fuzzy risk analysis algorithm for dealing with fuzzy risk analysis problems, where the values of the evaluating items are represented by interval-valued fuzzy numbers. The proposed method provides a useful way to deal with fuzzy risk analysis problems. [Copyright &y& Elsevier]

Abstract: A set cover for a set is a collection of special subsets whose union is . Given covers and for two sets, the set-cover difference problem is to construct a new cover for the elements covered by but not . Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation , which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers. [Copyright &y& Elsevier]

Abstract: The objective of this paper was to link a psychometric chart and Boolean algebra algorithms on deducing the procedural and logical issues of temperature–humidity environmental control for a grafted seedling acclimatization chamber. We developed a condition-sequence control circuit based on Boolean algebra algorithms to solve the complex logical problem existing in temperature–humidity environmental control procedures. A Matlab program was used to deduce and simplify the Boolean relations between input and output logical variables of the controller, whereas the correctness of Boolean function was verified by an Excel program. The Boolean functions were firstly transformed to switching (logical) circuits and subsequently transformed to a programmable logical controller (PLC) program systematically. We implemented the developed industrial wiring devices and PLC in designing a temperature–humidity environmental controller of an acclimatization chamber for grafted seedlings in that we adopted the nonlinear control technique associated with the condition-sequence control methodology as the main control scheme. On the other hand, we adopted the compound control action, two-position set point action, the time-delay control and the conditional action of free cooling as the main control operations for the controller. Our results demonstrate that the overall seasonal survival rate was 97% by using the Boolean algebra-based controlled chamber grafting, which was higher than that of 90% by employing the field grafted seedling operations. [Copyright &y& Elsevier]

Abstract: Given a finite set of nonnegative integers with no three-term arithmetic progressions, the Stanley sequence generated by , denoted as , is the infinite set created by beginning with and then greedily including strictly larger integers which do not introduce a three-term arithmetic progression in . Erdős et al. asked whether the counting function, , of a Stanley sequence satisfies for every and . In this paper we answer this question in the affirmative; in fact, we prove the slightly stronger result that for . [Copyright &y& Elsevier]