Narrow Results

We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.

Inspired by a real-life application, we investigate the computationally hard problem of extending a precoloring of an interval graph to a proper coloring under some bound on the number of available colors. We are interested in quickly determining whether or not such an extension exists on instances occurring in practice in connection with campsite bookings on a campground. A naive exhaustive search does not terminate in reasonable time. We have formulated a new approach which moves the computation time within the usable range on all the data samples available to us.

We present algorithms that construct a sparse spanning subgraph of a three-edge-connected graph that preserves three-edge connectivity or of a three-vertex-connected graph that preserves three-vertex connectivity. Our algorithms are conceptually simple and run in O(|E|) time. These simple algorithms can be used to improve the efficiency of the best-known algorithms for three-edge and three-vertex connectivity and their related problems, by preprocessing the input graph so as to trim it down to a sparse graph. Afterwards, the original algorithms run in O(|V|) instead of O(|E|) time. Our algorithms generate an adjacency-lists structure to represent the sparse spanning subgraph, so that when a depth-first search is performed over the subgraph based on this adjacency-lists structure it actually traverses the paths in an ear-decomposition of the subgraph. This is useful because many of the existing algorithms for three-edge- or three-vertex connectivity and their related problems are based on an ear-decomposition of the given graph. Using such an adjacency-lists structure to represent the input graph would greatly improve the run-time efficiency of these algorithms.

Given an undirected, connected, simple graph G = (V,E), two vertex labelings L_V and L'_V of the vertices of G, and a label flip operation that interchanges a pair of labels on adjacent vertices, the Vertex Relabeling Problem is to transform G from L_V into L'_V using the flip operation. Agnarsson et al. showed solving the Vertex Relabeling Problem on arbitrary graphs can be done in θ(n²), where n is the number of vertices in G. In this article we study the Vertex Relabeling Problem on graphs K_m,m and introduce the concept of parity and precise labelings. We show that, when we consider the parity labeling, the problem on graphs K_m,m can be solved quickly in O(log m) time using m processors on an EREW PRAM. Additionally, we also show that the number of processors can be further reduced to in this case while the time complexity does not change. When the labeling is precise, the parallel time complexity increases by a factor of log m while the processor complexities remain m and . We also show that, when graphs are restricted to K_m,m, this problem can be solved optimally in O(m) time when the labeling is parity, and can be solved in O(m log m) time when the labeling is precise, thereby improving the result in Agnarsson et al. for this specific case. Moreover, we generalize the result in the case of precise labeling to the cases when L_V and L'_V can be any configuration. In the end we give a conclusion and a list of some interesting open problems.

In this paper we consider the following game: players must alternately color the lowest numbered uncolored vertex of a given graph G= ({1, 2,…, n}, E) with a color, taken from a given set C, such that two adjacent vertices are never colored with the same color. In one variant, the first player which is unable to move, loses the game. In another variant, player 1 wins the game if and only if the game ends with all vertices colored. We show that for both variants, the problem of determining whether there is a winning strategy for player 1 is PSPACE-complete for any C with |C|≥3, but the problems are solvable in , and time, respectively, if |C|=2. We also give polynomial time algorithms for the problems with certain restrictions on the graphs and orderings of the vertices. We give some partial results for the versions where no order for coloring the vertices is specified.

It is shown, that for each constant k≥1, the following problems can be solved in time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge disjoint cycles, determine whether G has a feedback vertex set of size ≤k. Also, every class , that is closed under minor taking, taking, and that does not contain the graph consisting of k disjoint copies of K₃, has an membership test algorithm.

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC¹. This is done by showing that 3-colouring a linked list is NC¹-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC¹.

For the CRCW PRAM model, an o(log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o(log n) chromatic number and a known interval representation. In particular, when the chromatic number is O((log n)^1-ε), 0<ε<1, the algorithm runs in O(log n/log log n) time. Also, an O(log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω(log n/log log n) time, on a CRCW PRAM, with a polynomial number of processors.

We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+nlog n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.

Graph algorithms are becoming increasingly important for solving many problems in scientific computing, data mining and other domains. As these problems grow in scale, parallel computing resources are required to meet their computational and memory requirements. Unfortunately, the algorithms, software, and hardware that have worked well for developing mainstream parallel scientific applications are not necessarily effective for large-scale graph problems. In this paper we present the inter-relationships between graph problems, software, and parallel hardware in the current state of the art and discuss how those issues present inherent challenges in solving large-scale graph problems. The range of these challenges suggests a research agenda for the development of scalable high-performance software for graph problems.

We provide self-stabilizing algorithms to obtain and maintain a maximal matching, maximal independent set or minimal dominating set in a given system graph. They converge in linear rounds under a distributed or synchronous daemon. They can be implemented in an ad hoc network by piggy-backing on the beacon messages that nodes already use.

This paper presents a VLSI array for labeling the connected components of a graph on N nodes in O(r) steps using a reconfigurable bus of width m bits, such that and 1≤r≤m. The network architecture consists of an array of simple logic nodes which are connected by a reconfigurable bus. To solve a problem on N nodes, the array uses N processors and N(N−1)/2 switches. The proposed connectivity and transitive closure algorithms are based on a processor indexing scheme which employs constant-weight codes. It is shown that when r is a constant, then the algorithm takes O(1) time using a bus of width O(N^1/r), and when r=[log N/ loglog N], the algorithm takes O(log N/ loglog N) time using a bus of width O(log N) bits.

This paper presents a randomized parallel algorithm for the Maximal Independent Set problem. Our algorithm uses a BSPlike computer with p processors and requires that for a graph with n vertices and m edges. Under this scalability assumption, and after a preprocessing phase, it computes a maximal independent set after O(log p) communication rounds, with high probability, each round requiring linear computation time . The preprocessing phase is deterministic and important in order to ensure that degree computations can be implemented efficiently. For this, we give an optimal parallel BSPCGM algorithm to the p-quantiles search problem, which runs in time and a constant number of communication rounds, and could be of interest in its own right, as shown in the text.

Algorithms to calculate the fractal dimension of a complex network are presented. One of the algorithms is applied to a parametrized class of models whose fractal dimension transitions from one to two. For the system size we considered here (16384 nodes), the transition takes place from one at p = 0 to essentially two at the small value p = 0.03. This seems to indicate that the transition is likely to become infinitely sharp and occur at p = 0 as the system size increases to infinity.

This paper presents the ideas, experiments and specifications related to the Supervised TextRank (STR) technique, a word tagging method based on the TextRank algorithm. The main innovation of STR technique is the use of a graph-based ranking algorithm similar to PageRank in a supervised fashion, gathering the information needed to build the graph representations of the text from a tagged corpus. We also propose a flexible graph specification language that allows to easily experiment with multiple configurations for the topology of the graph and for the information associated to the nodes and the edges. We have carried experiments in the Part-Of-Speech task, a common tagging problem in Natural Language Processing. In our best result we have achieved a precision of 96.16%, at the same level of the best tagging tools.

miRNAs are involved in many critical cellular activities through binding to their mRNA targets, e.g. in cell proliferation, differentiation, death, growth control, and developmental timing. Accurate prediction of miRNA targets can assist efficient experimental investigations on the functional roles of miRNAs. Their prediction, however, remains a challengeable task due to the lack of experimental data about the tertiary structure of miRNA-target binding duplexes. In particular, correlations of nucleotides in the binding duplexes may not be limited to the canonical Watson Crick base pairs (BPs) as they have been perceived; methods based on secondary structure prediction (typically minimum free energy (MFE)) have only had mix success. In this work, we characterized miRNA binding duplexes with a graph model to capture the correlations between pairs of nucleotides of an miRNA and its target sequences. We developed machine learning algorithms to train the graph model to predict the target sites of miRNAs. In particular, because imbalance between positive and negative samples can significantly deteriorate the performance of machine learning methods, we designed a novel method to re-sample available dataset to produce more informative data learning process.

We evaluated our model and miRNA target prediction method on human miRNAs and target data obtained from mirTarBase, a database of experimentally verified miRNA-target interactions. The performance of our method in target prediction achieved a sensitivity of 86% with a false positive rate below 13%. In comparison with the state-of-the-art methods miRanda and RNAhybrid on the test data, our method outperforms both of them by a significant margin.

The source codes, test sets and model files all are available at http://rna-informatics.uga.edu/?f=software&p=GraB-miTarget.

In this paper, we demonstrate that it is possible to create an adiabatic quantum computing algorithm that solves the shortest path between any two vertices on an undirected graph with at most $3V$ qubits, where $V$ is the number of vertices of the graph. We do so without relying on any classical algorithms, aside from creating an ($V\times V$) adjacency matrix. The objective of this paper is to demonstrate the fact that it is possible to model large graphs on an adiabatic quantum computer using the maximum number of qubits available and random graph generators such as the Barabási–Albert and the Erdős–Rényi methods which can scale based on a power law.

We show that the best possible worst case competitive ratio of any deterministic algorithm for weighted online roommates problem is arbitrarily close to 4. This proves that the 4-competitive algorithm proposed by Bernstein and Rajagopalan [3] for the weighted version of the online roommates problem actually attains the best possible competitive ratio.

A 2-matching in an undirected graph G = (VG, EG) is a function x: EG → {0, 1, 2} such that for each node v ∈ VG the sum of values x(e) for all edges e incident to v does not exceed 2. The size of x is the sum ∑_e x(e). If {e ∈ EG|x(e) ≠ 0} contains no triangles then x is called triangle-free.

Cornuéjols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a maximum triangle free 2-matching of size (hereinafter n ≔ |VG|, m ≔ |EG|) and also established a min-max theorem.

We claim that this approach is, in fact, superfluous by demonstrating how these results may be obtained directly from the Edmonds–Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in time. Also we give a short self-contained algorithmic proof of the min-max theorem.

Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every d-regular graph (for d ≥ 3) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a d-regular graph: an O(n)-algorithm for d = 3, an O(m + n^3/2)-algorithm for d = 2k(k ≥ 2), and an O(n²)-algorithm for d = 2k + 1(k ≥ 2).

We also prove that there exists a constant c > 1 such that every 3-regular graph contains at least cⁿ perfect triangle-free 2-matchings.

A set M ⊆ E is called an acyclic matching of a graph G = (V, E) if no two edges in M are adjacent and the subgraph induced by the set of end vertices of the edges of M is acyclic. Given a positive integer k and a graph G = (V, E), the acyclic matching problem is to decide whether G has an acyclic matching of cardinality at least k. Goddard et al. (Discrete Math.293(1–3) (2005) 129–138) introduced the concept of the acyclic matching problem and proved that the acyclic matching problem is NP-complete for general graphs. In this paper, we propose an O(n + m) time algorithm to find a maximum cardinality acyclic matching in a chain graph having n vertices and m edges and obtain an expression for the number of maximum cardinality acyclic matchings in a chain graph. We also propose a dynamic programming-based O(n + m) time algorithm to find a maximum cardinality acyclic matching in a bipartite permutation graph having n vertices and m edges. Finally, we strengthen the complexity result of the acyclic matching problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs.

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n²) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n²) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n²) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).