Search

In a distributed computing environment a faulty node could lead other nodes in the system to behave in a faulty manor. An initial set of faults could make all the nodes in the system become faulty. Such a set is called an irreversible dynamo. This is modelled as spreading a message among individuals V in a community ]> where E represents the acquaintance relation. A particular individual will believe a message if some of the individual΄s acquaintances believe the same and forward the believed messages to its neighbours. We are interested in finding the minimum set of initial individuals to be considered as convinced, called the min-seed, such that every individual in the community is finally convinced. We solve for min-seed on some special classes of graphs and then give an upper bound on the cardinality of the min-seed for arbitrary undirected graphs. We consider some interesting variants of the problem and analyse their complexities and give some approximate algorithms. [ABSTRACT FROM AUTHOR]

In this paper we introduce module-composed graphs, i.e. graphs which can be defined by a sequence of one-vertex insertions v1,...,vn, such that the neighbourhood of vertex vi, 2 ≤ i ≤ n, forms a module of the graph defined by vertices v1,...,vi − 1. We show that module-composed graphs are HHDS-free and thus homogeneously orderable, weakly chordal, and perfect. Every bipartite distance hereditary graph and every trivially perfect graph is module- composed. We give an ]> time algorithm to decide whether a given graph G = (V,E) is module-composed and construct a corresponding module-sequence. For the case of bipartite graphs, we show that the set of module-composed graphs is equivalent to the well known class of distance hereditary graphs, which implies linear time algorithms for their recognition and construction of a corresponding module-sequence using BFS and Lex-BFS. [ABSTRACT FROM AUTHOR]

The study of evolution has become an important research issue, especially in the last decade, due to a greater awareness of our world΄s volatility. As a consequence, a new paradigm has emerged to respond more effectively to a class of new problems in Data Mining. In this paper we address the problem of monitoring the evolution of clusters and propose the MClusT framework, which was developed along the lines of this new Change Mining paradigm. MClusT includes a taxonomy of transitions, a tracking method based in Graph Theory, and a transition detection algorithm. To demonstrate its feasibility and applicability we present real world case studies, using datasets extracted from Banco de Portugal and the Portuguese Institute of Statistics. We also test our approach in a benchmark dataset from TSDL. The results are encouraging and demonstrate the ability of MClusT framework to provide an efficient diagnosis of clusters transitions. [ABSTRACT FROM AUTHOR]

We characterize optimal bipartite expander graphs and give necessary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs that are also bipartite Ramanujan graphs. In particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k ≥ 2, a graph G = (V,E) is Pk-bicolorable if its vertex set V can be partitioned into two subsets (i.e., colors) V1 and V2 such that for every induced Pk (i.e., path with exactly k − 1 edges and k vertices) in G, the two colors alternate along the Pk, i.e., no two consecutive vertices of the Pk belong to the same color Vi, i = 1,2. Obviously, a graph is bipartite if and only if is P2-bicolorable, every graph is Pk-bicolorable for some k and if G is Pk-bicolorable then it is Pk + 1-bicolorable. The notion of Pk-bicolorable graphs is motivated by a similar notion of cycle-bicolorable graphs introduced in connection with chordal probe graphs. Moreover, P3- and P4-bicolorable graphs are closely related to various other concepts such as 2-subcolorable graphs, P4-bipartite graphs and alternately orientable graphs. We give a structural characterization of P3-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of P4-bicolorable graphs in terms of forbidden subgraphs. [ABSTRACT FROM AUTHOR]

A procedure of control synthesis for DES (discrete-event systems) modelled by the special class of place/transition Petri nets (P/T PNs), the so called state machines (SMs), is introduced here, generalized and extended for DES modelled by P/T PNs with general structure. Its applicability to the automatic DES control synthesis is presented as well as the possibility of its utilizing at supervision of the agent cooperation in multi-agent systems (MAS). For modelling the agents P/T PNs are utilized too. The usefulness of the approach is demonstrated by examples. [ABSTRACT FROM AUTHOR]

In this paper we investigate the users΄ recommendation networks based on the large data set from the Internet Movie Database. We study networks based on two types of inputs: first (monopartite) generated directly from the recommendation lists on the website, and second (bipartite) generated through the users΄ habits. Using a threshold number of votes per movie to filter the data, we actually introduce a control parameter, and then by tuning this parameter we study its effect on the network structure. From the detailed analysis of both networks we find that certain robust topological features occur independently from the value of the control parameter. We also present a comparison of the network clustering and shortest paths on the graphs with a randomized network model based on the same data. [ABSTRACT FROM AUTHOR]

A near perfect matching in a graph G is a matching covering all but one vertex in G. If any n independent edges in G are contained in a near perfect matching where n≤(|V (G)|-2)/2, then G is said to be defect n-extendable. In this paper, we give out the extendability of the graph by deleting an edge from a defect n-extendable bipartite graph and also show that all the bounds given in the paper are sharp. [ABSTRACT FROM AUTHOR]

This paper studies the problem of making a bipartite graph 1-extendable by adding the smallest number of new edges that preserve bipartiteness. Let G = (V,E) be a graph with at least 2k+2 vertices. A matching is a subset of E(G) of which the edges are disjoint. A matching with k edges is called to be k-matching. If G has a k-matching and every k-matching is contained in a perfect matching, then G is said to be k-extendable. This problem finds application in the circuit design of allocating jobs to processors while one job specifies one machine to process. We present an O(|V|+|E|) algorithm to augment a bipartite graph to be 1-extendable. [ABSTRACT FROM AUTHOR]

The article provides information on matching problems. It form an important branch of graph theory. It also form a class of integer linear programming problems which can be solved in polynomial time. It discusses matching on bipartite graphs. It explains job scheduling. It examines the close connection between arc routing problems and matching.

A definition of the term "transportation problem" is presented. A transportation problem is a linear programming problem. A bipartite graph is the network representation of a special network problem. The transportation simplex method can be used to solve transportation problems. Specialized network algorithms can also be used to solve the problem.

A definition of the term "bipartite graph" is presented. It refers to a graph or network whose nodes can be partitioned into two subsets such that its edges connect a node in each partition.