Search

A given special case of NP-complete scheduling problem can be approximated by solving a special case of similar problem with the same precedence graph. We construct a metric space over a set of special cases of this problem and consider the statistical relationship between distance between a pair of special cases of the under consideration and the average error of the approximated solution. Sethi, Gabow, Coffman's and Fujii's algorithms for this problem are used. It is shown that the absolute and the relative error of the objective function decreases over the density of a graph with a fixed number of jobs. In general case, relative non-zero error value increases with the number of jobs. [ABSTRACT FROM AUTHOR]

Let k 1 be an integer, and let G be a finite and simple graph with vertex set V (G). A signed total Italian k-dominating function on a graph G is a function f: V (G) ! f1; 1; 2g such that P u2N(v) f(u) ≥ k for every v 2 V (G), where N(v) is the neighborhood of v, and each vertex u with f(u) = 1 is adjacent to a vertex v with f(v) = 2 or to two vertices w and z with f(w) = f(z) = 1. A set ff1; f2;: ::; fdg of distinct signed total Italian k-dominating functions on G with the property that Pd i=1 fi(v) ≤ k for each v 2 V (G), is called a signed total Italian k-dominating family (of functions) on G. The maximum number of functions in a signed total Italian k-dominating family on G is the signed total Italian k-domatic number of G, denoted by dk stI (G). In this paper we initiate the study of signed total Italian k-domatic numbers in graphs, and we present sharp bounds for dk stI (G). In addition, we determine the signed total Italian k-domatic number of some graphs. [ABSTRACT FROM AUTHOR]

Phylogenetic networks generalize phylogenetic trees by allowing the modelization of events of reticulate evolution. Among the different kinds of phylogenetic networks that have been proposed in the literature, the subclass of binary tree-child networks is one of the most studied ones. However, very little is known about the combinatorial structure of these networks. In this paper we address the problem of generating all possible binary tree-child (BTC) networks with a given number of leaves in an efficient way via reduction/augmentation operations that extend and generalize analogous operations for phylogenetic trees, and are biologically relevant. Since our solution is recursive, this also provides us with a recurrence relation giving an upper bound on the number of such networks. We also show how the operations introduced in this paper can be employed to extend the evolutive history of a set of sequences, represented by a BTC network, to include a new sequence. An implementation in python of the algorithms described in this paper, along with some computational experiments, can be downloaded from . [ABSTRACT FROM AUTHOR]

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and Sfragara published a breakthrough paper about irregular normal and directed degree sequences for which rapid mixing of the swap Markov chain is proved. In this paper we present two groups of results. An example from the first group is the following theorem: let be a directed degree sequence on n vertices. Denote by Δ the maximum value among all in- and out-degrees and denote by the number of edges in the realization. Assume furthermore that . Then the swap Markov chain on the realizations of is rapidly mixing. This result is a slight improvement on one of the results of Greenhill and Sfragara. An example from the second group is the following: let d be a bipartite degree sequence on the vertex set U ⊎ V, and let 0 < c1 ≤ c2 < |U| and 0 < d1 ≤ d2 < |V| be integers, where c1 ≤ d(v) ≤ c2: ∀v ∈ V and d1 ≤ d(u) ≤ d2: ∀u ∈ U. Furthermore assume that (c2 − c1 − 1)(d2 − d1 − 1) < max{c1(|V| − d2), d1(|U| − c2)}. Then the swap Markov chain on the realizations of d is rapidly mixing. A straightforward application of this latter result shows that when a random bipartite or directed graph is generated under the Erdős—Rényi G(n, p) model with mild assumptions on n and p then the degree sequence of the generated graph has, with high probability, a rapidly mixing swap Markov chain on its realizations. [ABSTRACT FROM AUTHOR]

Geometric approaches to network analysis combine simply defined models with great descriptive power. In this work we provide a method for embedding directed acyclic graphs (DAG) into Minkowski spacetime using Multidimensional scaling (MDS). First we generalise the classical MDS algorithm, defined only for metrics with a Riemannian signature, to manifolds of any metric signature. We then use this general method to develop an algorithm which exploits the causal structure of a DAG to assign space and time coordinates in a Minkowski spacetime to each vertex. As in the causal set approach to quantum gravity, causal connections in the discrete graph correspond to timelike separation in the continuous spacetime. The method is demonstrated by calculating embeddings for simple models of causal sets and random DAGs, as well as real citation networks. We find that the citation networks we test yield significantly more accurate embeddings that random DAGs of the same size. Finally we suggest a number of applications in citation analysis such as paper recommendation, identifying missing citations and fitting citation models to data using this geometric approach. [ABSTRACT FROM AUTHOR]

A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i(G + uv) < k for any pair of non-adjacent vertices u and v of G. The problem that arises is that of characterizing k-i critical graphs. In this paper, we characterize connected 3-i-critical graphs with minimum vertex cutset of size 2. More specifically, we show that if G is a connected 3-i-critical graph with minimum vertex cutset S of size 2 and the number of components of G−S is exactly two, then G is isomorphic to a graph in one of nine classes of connected 3-i-critical graphs. The results in this paper together with results in [1] and [2] provide a complete characterization of connected 3-i-critical graphs with a minimum cutset of size at most 3. [ABSTRACT FROM AUTHOR]

Let $${\mathcal {F}}$$ be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that $$G-S$$ belongs to $${\mathcal {F}}$$ , is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when $${\mathcal {F}}$$ is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {O}(1)}$$ for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. [ABSTRACT FROM AUTHOR]

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n2). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms. [ABSTRACT FROM AUTHOR]

Let G = (V;E) be a given graph of order n. A function f: V ! f0; 1; 2g is an independent Roman dominating function (IRDF) on G if for every vertex v 2 V with f(v) = 0 there is a vertex u adjacent to v with f(u) = 2 and fv 2 V: f(v) > 0g is an independent set. The weight of an IRDF f on G is the value f(V) = P v2V f(v). The minimum weight of an IRDF among all IRDFs on G is called the independent Roman domination number of G. In this paper, we give algorithms for computing the independent Roman domination number of G in O(jV j) time when G = (V;E) is a tree, unicyclic graph or proper interval graph. [ABSTRACT FROM AUTHOR]

Trace nets are a generalization of elementary nets, proposed by Badouel and Darondeau. They admit phenomena, unknown in traditional nets. For instance, in trace nets does not hold the "diamond property". For this reason, we propose a more precise definition of conflict, applicable to trace nets, and study occurrences of conflicts and existence of conflict-free runs in such nets. Main result of the paper says that any just computation in a trace net, starting from a conflict state, contains a conflict step. This result allows to construct an algorithm, selecting only conflict-free just computations from among all computations of a given net. All results of the paper hold for elementary nets, as they are a subclass of trace nets. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

The notion of degree-constrained spanning hierarchies, also called k-trails, was recently introduced in the context of network routing problems. They describe graphs that are homomorphic images of connected graphs of degree at most k. First results highlight several interesting advantages of k-trails compared to previous routing approaches. However, so far, only little is known regarding computational aspects of k-trails. In this work we aim to fill this gap by presenting how k-trails can be analyzed using techniques from algorithmic matroid theory. Exploiting this connection, we resolve several open questions about k-trails. In particular, we show that one can recognize efficiently whether a graph is a k-trail, and every graph containing a k-trail is a (k+1)-trail. Moreover, further leveraging the connection to matroids, we consider the problem of finding a minimum weight k-trail contained in a graph G. We show that one can efficiently find a (2k-1)-trail contained in G whose weight is no more than the cheapest k-trail contained in G, even when allowing negative weights. The above results settle several open questions raised by Molnár, Newman, and Sebő. [ABSTRACT FROM AUTHOR]

In applications there are networks with unreliable nodes. To construct models of such networks and effective algorithms of their analysis in this paper some elements from the graph theory, the algebra, the sets theory and the probability theory are combined. These constructions allow to investigate oriented graphs with unreliable nodes using as accuracy so asymptotic formulas. All constructed algorithms have a linear complexity by a number of graph nodes [ABSTRACT FROM AUTHOR]

For railway operators, one of many important goals is to improve the utilization efficiency of electric multiple units (EMUs). When operators design EMU circulation plans, EMU type restrictions are critical factors when assigning EMUs to the correct depots for maintenance. However, existing studies only consider that EMUs are maintained at their home depots. However, targeting that problem, in this paper, an optimization model for the EMU circulation planning problem that allows depots to be selected for EMU maintenance is proposed. This model aims at optimizing the number of used EMUs and the number of EMU maintenance tasks and simultaneously incorporates other important constraints, including type restrictions, on EMU maintenance and night accommodation capacity at depots. In order to solve the model, a branch-and-price algorithm is also developed. A case study of a real-world high-speed railway was conducted to compare and analyze the effects of different maintenance location constraints. The results show that the number of EMUs used will decrease under the maintenance sharing scheme, the number of EMU maintenance tasks can be reduced, and the time occupied in EMU maintenance will be released. In addition, the scheme of maintenance resources sharing and increases to mileage limits can effectively decrease the number of EMU maintenance tasks significantly. The model and algorithm can be used as an effective quantitative analysis tool for railway operators' decision-making processes in the EMU circulation planning problem. [ABSTRACT FROM AUTHOR]

Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search based methods for graph drawing which are based on optimizing an objective function which is formed from a weighted sum of multiple criteria. In this paper, we propose a new neighbourhood search method which uses a tabu search coupled with path relinking to optimize such objective functions for general graph layouts with undirected straight lines. To our knowledge, before our work, neither of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimization techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (objective function’s value) and the speed of layout in terms of the number of evaluated solutions required to draw a graph. We also examine the relative scalability of each method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can layout larger graphs than the state-of-the-art neighbourhood search methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset. [ABSTRACT FROM AUTHOR]

There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of 'right angle crossing (RAC)' drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of 'outer-1-plane' graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

Compound digraphs are a widely used model in computer science. In many application domains these models evolve over time. Only few approaches to visualize such dynamic compound digraphs exist and mostly use animation to show the dynamics. In this paper we present a new visualization tool called TimeArcTrees that visualizes weighted, dynamic compound digraphs by drawing a sequence of node-link diagrams in a single view. Compactness is achieved by aligning the nodes of a graph vertically. Edge crossings are reduced by drawing upward and downward edges separately as colored arcs. Horizontal alignment of the instances of the same node in different graphs facilitates comparison of the graphs in the sequence. Many interaction techniques allow to explore the given graphs. Smooth animation supports the user to better track the transitions between views and to preserve his or her mental map. We illustrate the usefulness of the tool by looking at the particular problem of how shortest paths evolve over time. To this end, we applied the system to an evolving graph representing the German Autobahn and its traffic jams. [ABSTRACT FROM AUTHOR]

Graph-Coloring problem (GCP) deals with assigning labels (colors) to the vertices of a graph such that adjacent vertices do not get the same color. Coloring a graph with minimum number of colors is a well-known NP-hard problem. In this paper a new permutation based representation of graph coloring problem is solved using a parallel genetic algorithm (PGA). Migration model of parallelism is used with Message passing interface (MPI) for implementation of parallel genetic algorithm. Three-crossover operators namely greedy partition crossover (GPX), Uniform independent set crossover (UISX), and Permutation-based crossover (PX) are used. The performance of the three crossover operators is investigated in terms of convergence and execution time for standard benchmark graphs. The results show that GPX performs well in terms of convergence and PX in terms of execution time. The three crossover operators in parallel genetic algorithm outperform the serial genetic algorithm approximately by a factor of three. The paper is also validated with the static wavelength assignment problem in optical networks. [ABSTRACT FROM AUTHOR]

In this paper, we study the fault diagnosis problem for distributed discrete event systems. The model assumes that the system is composed of distributed components that are modeled in labeled Petri nets and interact with each other via sets of common resources (places). Further, a component's own access to a common resource is an observable event. Based on the diagnoser approach proposed by Sampath et al, a distributed fault diagnosis algorithm with communication is presented. The distributed algorithm assumes that the local diagnosis process can exchange messages upon the occurrence of observable events. We prove the distribute diagnosis algorithm is correct in the sense that it recovers the same diagnostic information as the centralized diagnosis algorithm. And then, the OBDD (Ordered Binary Decision Diagrams) is introduced to manage the state explosion problem in state estimation of the system. [ABSTRACT FROM AUTHOR]

Let G =( V , E ) be a graph with vertex set V of size n and edge set E of size m . A vertex v ? V is called a hinge vertex if there exist two vertices in V \{ v } such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O ( n 2 ) time complexity and O ( m ) message complexity. In particular, the total messages exchanged during the algorithm are at most 2 m (log n + n log n +1) bits. [ABSTRACT FROM AUTHOR]

Consider the 2n (or O(n²)) min-cut problems on a graph with n nodes and nonnegative edge weights. Gomory and Hu [J. Soc. Indust. Appl. Math., 9 (1961), pp. 551–570] showed (essentially) that there are at most n-1 different min-cuts. They also described a compact structure (the flow equivalent tree) of size O(n) with the following property: for any pair of nodes, the value of a min-cut can be obtained from this structure. Furthermore, they showed how this structure can be found by solving only n - 1 min-cut problems. This paper contains generalizations of these results. For example, consider a k-terminal cut problem on a graph: for a given set of k nodes, delete a minimum weight set of edges (called a k-cut) so that each of the k nodes is in a different component. There are kn (or O(nk)) such problems. Hassin [Math. Oper. Res., 13 (1988), pp. 535–542] showed (essentially) that there are at most k-1n-1 (or O(nk-1)) different min k-cuts. We describe a compact structure of size O(nk-1) with the following property: for any k nodes, the value of a min k-cut can be obtained from this structure. We also show how this structure can be found by solving only k-1n-1 k-terminal cut problems. This work builds upon the results of Hassin [Math. Oper. Res., 13 (1988), pp. 535–542], [Oper. Res. Lett., 9 (1990), pp. 315–318], and [Lecture Notes in Comput. Sci. 450, 1990, pp. 228–299]. [ABSTRACT FROM AUTHOR]

The estimation of the correct number of dimensions is a long-standing problem in psychometrics. Several methods have been proposed, such as parallel analysis (PA), Kaiser-Guttman’s eigenvalue-greater-than-one rule, multiple average partial procedure (MAP), the maximum-likelihood approaches that use fit indexes as BIC and EBIC and the less used and studied approach called very simple structure (VSS). In the present paper a new approach to estimate the number of dimensions will be introduced and compared via simulation to the traditional techniques pointed above. The approach proposed in the current paper is called exploratory graph analysis (EGA), since it is based on the graphical lasso with the regularization parameter specified using EBIC. The number of dimensions is verified using the walktrap, a random walk algorithm used to identify communities in networks. In total, 32,000 data sets were simulated to fit known factor structures, with the data sets varying across different criteria: number of factors (2 and 4), number of items (5 and 10), sample size (100, 500, 1000 and 5000) and correlation between factors (orthogonal, .20, .50 and .70), resulting in 64 different conditions. For each condition, 500 data sets were simulated using lavaan. The result shows that the EGA performs comparable to parallel analysis, EBIC, eBIC and to Kaiser-Guttman rule in a number of situations, especially when the number of factors was two. However, EGA was the only technique able to correctly estimate the number of dimensions in the four-factor structure when the correlation between factors were .7, showing an accuracy of 100% for a sample size of 5,000 observations. Finally, the EGA was used to estimate the number of factors in a real dataset, in order to compare its performance with the other six techniques tested in the simulation study. [ABSTRACT FROM AUTHOR]

As a sustainable transportation mode, high-speed railway (HSR) has become an efficient way to meet the huge travel demand. However, due to the high acquisition and maintenance cost, it is impossible to build enough infrastructure and purchase enough train-sets. Great efforts are required to improve the transport capability of HSR. The utilization efficiency of train-sets (carrying tools of HSR) is one of the most important factors of the transport capacity of HSR. In order to enhance the utilization efficiency of the train-sets, this paper proposed a train-set circulation optimization model to minimize the total connection time. An innovative two-stage approach which contains segments generation and segments combination was designed to solve this model. In order to verify the feasibility of the proposed approach, an experiment was carried out in the Beijing-Tianjin passenger dedicated line, to fulfill a 174 trips train diagram. The model results showed that compared with the traditional Ant Colony Algorithm (ACA), the utilization efficiency of train-sets can be increased from 43.4% (ACA) to 46.9% (Two-Stage), and 1 train-set can be saved up to fulfill the same transportation tasks. The approach proposed in the study is faster and more stable than the traditional ones, by using which, the HSR staff can draw up the train-sets circulation plan more quickly and the utilization efficiency of the HSR system is also improved. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel image mosaicking method that is based on Speeded-Up Robust Features (SURF) of line segments, aiming to achieve robustness to incident scaling, rotation, change in illumination, and significant affine distortion between images in a panoramic series. Our method involves 1) using a SURF detection operator to locate feature points; 2) rough matching using SURF features of directed line segments constructed via the feature points; and 3) eliminating incorrectly matched pairs using RANSAC (RANdom SAmple Consensus). Experimental results confirm that our method results in high-quality panoramic mosaics that are superior to state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The approach presented in this paper presents a generalization of the currently fastest method for counting 5-node graphlets in bioinformatics. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and a cycle with four nodes, which are treated separately. Empirical analysis of running time agrees with the theoretical results. [ABSTRACT FROM AUTHOR]

This paper proposes a new methodology based on non-negative matrix factorization to detect communities and to identify central nodes in a network as well as within communities. The method is specifically designed for directed weighted networks and, consequently, it has been applied to the interbank network derived from the e-MID interbank market. In an interbank network indeed links are directed, representing flows of funds between lenders and borrowers. Besides distinguishing between Systemically Important Borrowers and Lenders, the technique complements the detection of systemically important banks, revealing the community structure of the network, that proxies the most plausible areas of contagion of institutions’ distress. [ABSTRACT FROM AUTHOR]

In the stock market, return reversal occurs when investors sell overbought stocks and buy oversold stocks, reversing the stocks’ price trends. In this paper, we develop a new method to identify key drivers of return reversal by incorporating a comprehensive set of factors derived from different economic theories into one unified dynamical Bayesian factor graph. We then use the model to depict factor relationships and their dynamics, from which we make some interesting discoveries about the mechanism behind return reversals. Through extensive experiments on the US stock market, we conclude that among the various factors, the liquidity factors consistently emerge as key drivers of return reversal, which is in support of the theory of liquidity effect. Specifically, we find that stocks with high turnover rates or high Amihud illiquidity measures have a greater probability of experiencing return reversals. Apart from the consistent drivers, we find other drivers of return reversal that generally change from year to year, and they serve as important characteristics for evaluating the trends of stock returns. Besides, we also identify some seldom discussed yet enlightening inter-factor relationships, one of which shows that stocks in Finance and Insurance industry are more likely to have high Amihud illiquidity measures in comparison with those in other industries. These conclusions are robust for return reversals under different thresholds. [ABSTRACT FROM AUTHOR]

Rooted phylogenetic networks are primarily used to represent conflicting evolutionary information and describe the reticulate evolutionary events in phylogeny. So far a lot of methods have been presented for constructing rooted phylogenetic networks, of which the methods based on the decomposition property of networks and by means of the incompatible graph (such as the C, the L and the BIMLR) are more efficient than other available methods. The paper will discuss and compare these methods by both the practical and artificial datasets, in the aspect of the running time of the methods and the effective of constructed phylogenetic networks. The results show that the L can construct much simper networks than the others. [ABSTRACT FROM AUTHOR]

Bender, Richmond, and Wormald showed that in almost all planar 3-connected triangulations (or dually, 3-connected cubic maps) with n edges, the largest 4-connected triangulation (or dually, the largest cyclically 4-edge-connected cubic component) has about n/2 edges [Random Structures Algorithms, 7 (1995), pp. 273-285]. In this paper, we derive some general results about the size of the largest component and apply them to a variety of types of planar maps. [ABSTRACT FROM AUTHOR]

In the "classical" network flow model. Flows are constrained by the capacities of individual arcs. In the "polymatroidal" network flow model introduced in this paper, flows are constrained by the capacities of sets of arcs. Yet the essential features of the classical model are retained: the augmenting path theorem, the integral flow theorem and the max flow min-cut theorem are all shown to yield to straightforward generalization. We describe a maximal flow algorithm which finds augmenting paths by labeling arcs instead of nodes, as in the case of the classical model. As a counterpart of a known result for the classical model, we prove that the number of augmentations required to achieve a maximal value flow is bounded by the cube of the number of arcs in the network, provided each successive augmentation is made along a shortest augmenting path, with ties between shortest paths broken by lexicography. [ABSTRACT FROM AUTHOR]

In this paper we describe new constructions for de Bruijn sequences and Perfect Factors. These constructions are all based upon the idea of constructing one sequence (or set of sequences) from another. As a result of this fact, the sequences obtained from these construction methods possess simple decoding algorithms based on decoding the sequences used to construct them. Such decoding algorithms are of importance in position-location applications. [ABSTRACT FROM AUTHOR]

Björner, Lovász and Shor introduced a chip-firing game on a finite graph $$G$$ as follows. We put some chips on each vertex of $$G$$ , we say that a vertex is ready if it has at least as many chips as its degree, in which case we can fire it and the result is that it distributes one chip to each of its neighbors, this may cause other vertices to be ready, and so on. This game continues until no vertex can be fired. In this paper, we study chip-firing games on complete graphs. We obtain a sufficient and necessary condition for chip-firing games on complete graphs to be finite. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph with degree sequence $$d_1,d_2,\ldots ,d_n$$ . Given a positive integer $$p$$ , denote by $$e_p(G)=\sum _{i=1}^n d_i^p$$ . Caro and Yuster introduced a Turán-type problem for $$e_p(G)$$ : given an integer $$p$$ , how large can $$e_p(G)$$ be if $$G$$ has no subgraph of a particular type. They got some results for the subgraph of particular type to be a clique of order $$r+1$$ and a cycle of even length, respectively. Denote by $$ex_p(n,H)$$ the maximum value of $$e_p(G)$$ taken over all graphs with $$n$$ vertices that do not contain $$H$$ as a subgraph. Clearly, $$ex_1(n,H)=2ex(n,H)$$ , where $$ex(n,H)$$ denotes the classical Turán number. In this paper, we consider $$ex_p(n, C_5)$$ and prove that for any positive integer $$p$$ and sufficiently large $$n$$ , there exists a constant $$c=c(p)$$ such that the following holds: if $$ex_p(n, C_5)=e_p(G)$$ for some $$C_5$$ -free graph $$G$$ of order $$n$$ , then $$G$$ is a complete bipartite graph having one vertex class of size $$cn+o(n)$$ and the other $$(1-c)n+o(n)$$ . [ABSTRACT FROM AUTHOR]

A connected graph $$G$$ is said to be factor-critical if $$G-v$$ has a perfect matching for every vertex $$v$$ of $$G$$ . Lovász proved that every factor-critical graph has an ear decomposition. In this paper, the ear decomposition of the factor-critical graphs $$G$$ satisfying that $$G-v$$ has a unique perfect matching for any vertex $$v$$ of $$G$$ with degree at least 3 is characterized. From this, the number of maximum matchings of factor-critical graphs with the special ear decomposition is obtained. [ABSTRACT FROM AUTHOR]

The energy of a simple graph $$G$$ , denoted by $$E(G)$$ , is defined as the sum of the absolute values of eigenvalues of $$G$$ . In this paper, we show that, among all subdivisions of graphs with $$n$$ vertices and chromatic number $$k$$ , the subdivision of the Turán graph $$T(n,k)$$ has the maximal energy. [ABSTRACT FROM AUTHOR]

Cohen-Macaulayness of bipartite graphs is investigated by several mathematicians and has been characterized combinatorially. In this paper, we give some different combinatorial conditions for a bipartite graph which are equivalent to Cohen-Macaulayness of the graph. We prove that a bipartite graph is Cohen-Macaulay if and only if it is well covered and has a unique perfect matching. We also provide a fast algorithm to check Cohen-Macaulayness of a given bipartite graph. [ABSTRACT FROM AUTHOR]

The coloring of disk graphs is motivated by the frequency assignment problem. In 1998, Malesińska et al. introduced double disk graphs as their generalization. They showed that the chromatic number of a double disk graph $$G$$ is at most $$33\,\omega (G) - 35$$ , where $$\omega (G)$$ denotes the size of a maximum clique in $$G$$ . Du et al. improved the upper bound to $$31\,\omega (G) - 1$$ . In this paper we decrease the bound substantially; namely we show that the chromatic number of $$G$$ is at most $$15\,\omega (G) - 14$$ . [ABSTRACT FROM AUTHOR]

Topological properties of networks are widely applied to study the link-prediction problem recently. Common Neighbors, for example, is a natural yet efficient framework. Many variants of Common Neighbors have been thus proposed to further boost the discriminative resolution of candidate links. In this paper, we reexamine the role of network topology in predicting missing links from the perspective of information theory, and present a practical approach based on the mutual information of network structures. It not only can improve the prediction accuracy substantially, but also experiences reasonable computing complexity. [ABSTRACT FROM AUTHOR]

Labeled graphs are widely used to model complex data in many domains, so subgraph querying has been attracting more and more attention from researchers around the world. Unfortunately, subgraph querying is very time consuming since it involves subgraph isomorphism testing that is known to be an NP-complete problem. In this paper, we propose a novel coding method for subgraph querying that is based on Laplacian spectrum and the number of walks. Our method follows the filtering-and-verification framework and works well on graph databases with frequent updates. We also propose novel two-step filtering conditions that can filter out most false positives and prove that the two-step filtering conditions satisfy the no-false-negative requirement (no dismissal in answers). Extensive experiments on both real and synthetic graphs show that, compared with six existing counterpart methods, our method can effectively improve the efficiency of subgraph querying. [ABSTRACT FROM AUTHOR]

In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures. [ABSTRACT FROM AUTHOR]

It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e, there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this paper generalizes this result to any nonplanar graph G provided G does not have a K 3,3 minor containing the given edge e. Ford and Fulkerson used their result to provide an efficient algorithm for solving the maximum-flow problem on planar graphs. As a corollary to the main result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs. [ABSTRACT FROM AUTHOR]

Dendritic river networks are fundamental elements in cartography, and the generalization of these river networks directly influences the quality of cartographic generalization. Automatic selection is a difficult and important process for river generalization that requires the consideration of semantic, geometric, topological, and structural characteristics. However, owing to a lack of effective use of river features, most existing methods lose important spatial distribution characteristics of rivers, thus affecting the selection result. Therefore, a hierarchical elimination selection method of dendritic river networks is proposed that consists of three steps. First, a directed topology tree (DTT) is investigated to realize the organization of river data and the intelligent identification of river structures. Second, based on the “180° hypothesis” and “acute angle hypothesis”, each river is traced in the upstream direction from its estuary to create the stroke connections of dendritic river networks based on a consideration of the river semantics, length, and angle features, and the hierarchical relationships of a dendritic river network are then determined. Finally, by determining the total number of selected rivers, a hierarchical elimination algorithm that accounts for density differences is proposed. The reliability of the proposed method was verified using sample data tests, and the rationality and validity of the method were demonstrated in experiments using actual data. [ABSTRACT FROM AUTHOR]

Let H be a set of undirected graphs. The induced H-packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H. In this paper we focus on the case when H consists of factor-critical graphs and a certain family of 'propellers'. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai-Edmonds type structure theorem and a Berge-Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans. [ABSTRACT FROM AUTHOR]

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) s1t1, s2t2, … , sktk, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion c > 1, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation. [ABSTRACT FROM AUTHOR]

Visualisation of taxonomies and sets has recently become an active area of research. Many application fields now require more than a strict classification of elements into a hierarchy tree. Euler diagrams, one of the most natural ways of depicting intersecting sets, may provide a solution to these problems. In this paper, we present an approach for the automatic generation of Euler-like diagrams. This algorithm differs from previous approaches in that it has no undrawable instances of input, allowing it to be used in systems where the output is always required. We also improve the readability of Euler diagrams through the use of Bézier curves and transparent coloured textures. Our approach has been implemented using the Tulip platform. Both the source and executable program used to generate the results are freely available. [ABSTRACT FROM AUTHOR]

The ability of using dispersed generation (DG) in the distribution system restoration service in the context of smart networks is presented in this paper. The objectives are to reduce the consequences due to a major blackout in terms of the out-of-service load volume, and the duration of restoration process. Based on knapsack problem formulation and network represented graph modeling, a new restoration procedure for distribution network is proposed. An adapted branch-and-bound algorithm is then used to solve the problem. It maximizes the restored loads in distribution by using the DG availability. Simulation results on a study case will be shown to illustrate the proposed procedure and quantify the benefit of using DG in critical situations. [ABSTRACT FROM AUTHOR]

For an arbitrary class of graphs $$\mathcal{G}$$ , there may not exist a function f such that $$\chi(G) \leq f(\omega(G))$$ , for every $$G \in \mathcal{G}$$ . When such a function exists, it is called a χ-binding function for $$\mathcal{G}$$ . The problem of finding an optimal χ-binding function for the class of 3 K 1-free graphs is open. In this paper, we obtain linear χ-binding function for the class of {3 K 1, H}-free graphs, where H is one of the following graphs: $$K_1 + C_4, (K_3 \cup K_1)+K_1, K_1 + P_4, K_4 \cup K_1$$ , House graph and Kite graph. We first describe structures of these graphs and then derive χ-binding functions. [ABSTRACT FROM AUTHOR]