Search

The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph have two "distinct" regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very "similar". En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht ([11]) and Lovász and Szegedy ([9,10]), from a previously known variant of the regularity lemma due to Alon et al.[2]. The proof also provides a deterministic polynomial time algorithm for finding such partitions. [ABSTRACT FROM AUTHOR]

When ties and incomplete preference lists are permitted in the Stable Marriage problem, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe a polynomial-time $\frac{8}{5}$-approximation algorithm for a variant in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralized matching schemes. [ABSTRACT FROM AUTHOR]

We investigate the problem of finding an unknown cut through querying vertices of a graph G. Our complexity measure is the number of submitted queries. To avoid some worst cases, we make a few assumptions which allow us to obtain an algorithm with the worst case query complexity of $O(k)+2k\log{n\over k}$ in which k is the number of vertices adjacent to cut-edges. We also provide a matching lowerbound and then prove if G is a tree our algorithm can asymptotically achieve the information theoretic lowerbound on the query complexity. Finally, we show it is possible to remove our extra assumptions but achieve an approximate solution. [ABSTRACT FROM AUTHOR]

We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a minimum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well. [ABSTRACT FROM AUTHOR]

We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k. [ABSTRACT FROM AUTHOR]

Greedy algorithms are simple, but their relative power is not well understood. The priority framework [5] captures a key notion of "greediness" in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions. We first provide a tight bound of α ≈ 0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β ≈ 0.780 and γ ≈ 0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ ≈ 0.893. [ABSTRACT FROM AUTHOR]

We give efficient distributed approximation algorithms for weighted versions of the maximum matching problem and the minimum dominating set problem for graphs from minor-closed families. To complement these results we indicate that no efficient distributed algorithm for the minimum weight connected dominating set exists. [ABSTRACT FROM AUTHOR]

We derive quadratic lower bounds on the *-complexity of sum-of-products-of-sums (ΣΠΣ) formulas for classes of polynomials f that have too few partial derivatives for the techniques of Shpilka and Wigderson [10,9]. This involves a notion of "resistance" which connotes full-degree behavior of f under any projection to an affine space of sufficiently high dimension. They also show stronger lower bounds over the reals than the complex numbers or over arbitrary fields. Separately, by applying a special form of the Baur-Strassen Derivative Lemma tailored to ΣΠΣ formulas, we obtain sharper bounds on + ,*-complexity than those shown for *-complexity by Shpilka and Wigderson [10], most notably for the lowest-degree cases of the polynomials they consider. [ABSTRACT FROM AUTHOR]

We consider constant depth circuits augmented with few exact threshold gates with arbitrary weights. We prove strong (up to exponential) size lower bounds for such circuits computing symmetric Boolean functions. Our lower bound is expressed in terms of a natural parameter, the balance, of symmetric functions. Furthermore, in the quasi-polynomial size setting our results provides an exact characterization of the class of symmetric functions in terms of their balance. [ABSTRACT FROM AUTHOR]

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks exhibit a power-law distribution: the number of nodes yi of a given degree i is proportional to i − β where β> 0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent β? Our main result is the proof that many classical NP-hard graph-theoretic optimization problems remain NP-hard on power law graphs for certain values of β. In particular, we show that some classical problems, such as CLIQUE and COLORING, remains NP-hard for all β ≥ 1. Moreover, we show that all the problems that satisfy the so-called "optimal substructure property" remains NP-hard for all β> 0. This includes classical problems such as MIN VERTEX-COVER, MAX INDEPENDENT-SET, and MIN DOMINATING-SET. Our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimization problems. [ABSTRACT FROM AUTHOR]

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute. [ABSTRACT FROM AUTHOR]

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a kO(dk)n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain Kh as a topological minor, we give an improved algorithm for the problem with running time (O(h))hkn. For graphs which are Kh-minor-free, the running time is further reduced to (O(logh))hk/2n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(n logn) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. [ABSTRACT FROM AUTHOR]

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the minimum broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for trees. It is proved that the complexity of the problem of determining the minimum broadcast time of any vertex in an arbitrary tree T = (V, E) is ΘV. In this paper we present an algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph G = (V, E) in O(V) time. This, combined with the obvious lower bound, gives a Θ(V) solution for the problem of broadcasting in unicyclic graphs. As a byproduct, we also find a broadcast center of the unicyclic graph (a vertex in G with the minimum broadcast time). [ABSTRACT FROM AUTHOR]

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n3), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n2 logn logΣ) and O(Σn2 log2n loglogn), with Σ denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The algorithm presented in the present paper does not need to resort to the FFT and yet is asymptotically faster than previously available ones. Specifically, an off-line algorithm is presented taking time O(Σn2), which is optimal for finite Σ. [ABSTRACT FROM AUTHOR]

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions. Q1: Where does the implication hold, and where does it fail?Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs?Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems?Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system? In short, we show that both parts of Q1 and Q2 can be answered with ‘everywhere', which generalize previous results by Pudlák and Beyersdorff. Regarding Q3, inequivalent canonical pairs tell that the proof systems are not "very similar", while equivalent, -inseparable canonical pairs tell that they are not "very different". We can relate Q4 to the open problem in structural complexity that asks whether unions of disjoint NP-complete sets are NP-complete. This demonstrates a new connection between proof systems, disjoint NP-pairs, and unions of disjoint -complete sets. [ABSTRACT FROM AUTHOR]

Many algorithms seek to compute actual optimal paths in weighted directed graphs. The standard approach for reporting an actual optimal path is based on building a single-source optimal path tree. A technique was given in [1] for a class of problems such that a single actual optimal path can be reported without maintaining any single-source optimal path tree, thus significantly reducing the space bound of those problems with no or little increase in their running time. In this paper, we extend the technique in [1] to the generalized problem of reporting many actual optimal paths with different starting and ending vertices in certain directed graphs. We show how this new technique yields improved results on several application problems, such as reconstructing a 3-D surface band bounded by two simple closed curves, finding various constrained segmentation of 2-D medical images, and circular string-to-string correction. Although the generalized many-path problem seems more difficult, our algorithms have nearly the same space and time bounds as those of the single-path cases. Our technique is likely to help improve other optimal paths or dynamic programming algorithms. We also correct an error in the time/space complexity for the circular string-to-string correction algorithm in [7] and give improved results for it. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for enumerating without repetitions all non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraints (i.e., some edges are required to be included in spanning trees). We will first prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the constrained smallest indexed triangulation which is obtained by extending the lexicographically ordered triangulation introduced by Bespamyatnikh. More specifically, we prove that all edge-constrained triangulations can be transformed to the smallest indexed triangulation among them by O(n2) times of greedy flips. Our enumeration algorithm generates each output graph in O(n2) time and O(n) space based on reverse search technique. [ABSTRACT FROM AUTHOR]

We introduce a new notion called Fourier-accessibility that allows us to precisely characterize the class of Boolean functions for which a standard greedy learning algorithm successfully learns all relevant attributes. If the target function is Fourier-accessible, then the success probability of the greedy algorithm can be made arbitrarily close to one. On the other hand, if the target function is not Fourier-accessible, then the error probability tends to one. Finally, we extend these results to the situation where the input data are corrupted by random attribute and classification noise and prove that greedy learning is quite robust against such errors. [ABSTRACT FROM AUTHOR]

We consider finding maximin strategies and equilibria of explicitly given extensive form games with imperfect information but with no moves of chance. We show that a maximin pure strategy for a two-player game with perfect recall and no moves of chance can be found in time linear in the size of the game tree and that all pure Nash equilibrium outcomes of a two-player general-sum game with perfect recall and no moves of chance can be enumerated in time linear in the size of the game tree. We also show that finding an optimal behavior strategy for a one-player game of no chance without perfect recall and determining whether an equilibrium in behavior strategies exists in a two-player zero-sum game of no chance without perfect recall are both NP-hard. [ABSTRACT FROM AUTHOR]

We introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size n for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size n for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths. [ABSTRACT FROM AUTHOR]

This paper deals with problems which fall into the domain of selfish scheduling: a protocol is in charge of building a schedule for a set of tasks without directly knowing their length. The protocol gets these informations from agents who control the tasks. The aim of each agent is to minimize the completion time of her task while the protocol tries to minimize the maximal completion time. When an agent reports the length of her task, she is aware of what the others bid and also of the protocol's algorithm. Then, an agent can bid a false value in order to optimize her individual objective function. With erroneous information, even the most efficient algorithm may produce unreasonable solutions. An algorithm is truthful if it prevents the selfish agents from lying about the length of their task. The central question in this paper is: "How efficient a truthful algorithm can be? We study the problem of scheduling selfish tasks on parallel identical machines. This question has been raised by Christodoulou et al [8] in a distributed system, but it is also relevant in centrally controlled systems. Without considering side payments, our goal is to give a picture of the performance under the condition of truthfulness. [ABSTRACT FROM AUTHOR]

We show how to count all minimum weighted dominating sets of a graph on n vertices in time . Our algorithm is a combination of branch and bound approach along with dynamic programming on graphs with bounded treewidth. To achieve bound we introduce a technique of measuring running time of our algorithm by combining measure and conquer approach with linear programming. [ABSTRACT FROM AUTHOR]

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitution. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n3) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n5) for general scoring schemes, O(n4logn) for concave scoring schemes and O(n4) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. [ABSTRACT FROM AUTHOR]

In a graph G = (V,E), a vertex subset S ⊆ V of size k is called c-isolated if it has less than c·k outgoing edges. We repair a nontrivially flawed algorithm for enumerating all c-isolated cliques due to Ito et al. [European Symposium on Algorithms 2005] and obtain an algorithm running in O(4c·c4·E) time. We describe a speedup trick that also helps parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s-plexes (a relaxation of the clique notion), pointing out a W[1]-hardness result and providing a fixed-parameter algorithm for enumerating isolated s-plexes. [ABSTRACT FROM AUTHOR]

We use the connection between resource-bounded dimension and the online mistake-bound model of learning to show that the following classes have polynomial-time dimension zero. 1The class of problems which reduce to nondense sets via a majority reduction.1The class of problems which reduce to nondense sets via an iterated reduction that composes a bounded-query truth-table reduction with a conjunctive reduction. As corollary, all sets which are hard for exponential time under these reductions are exponentially dense. The first item subsumes two previous results and the second item answers a question of Lutz and Mayordomo. Our proofs use Littlestone's Winnow2 algorithm for learning r-of-k threshold functions and Maass and Turán's algorithm for learning halfspaces. [ABSTRACT FROM AUTHOR]

It is shown that the traveling salesman problem for graphs of degree at most three with n vertices can be solved in time O(1.251n), improving the previous bound O(1.260n) by Eppstein. [ABSTRACT FROM AUTHOR]

Geometric intersection graphs are intensively studied both for their practical motivation and interesting theoretical properties. Many such classes are hard to recognize. We ask the question if imposing restrictions on the girth (the length of a shortest cycle) of the input graphs may help in finding polynomial time recognition algorithms. We give examples in both directions. First we present a polynomial time recognition algorithm for intersection graphs of polygons inscribed in a circle for inputs of girth greater than four (the general recognition problem is NP-complete). On the other hand, we prove that recognition of intersection graphs of segments in the plane remains NP-hard for graphs with arbitrarily large girth. [ABSTRACT FROM AUTHOR]

We investigate the maximum number of simple cycles and the maximum number of Hamiltonian cycles in a planar graph G with n vertices. Using the transfer matrix method we construct a family of graphs which have at least 2.4262n simple cycles and at least 2.0845n Hamilton cycles. Based on counting arguments for perfect matchings we prove that 2.3404n is an upper bound for the number of Hamiltonian cycles. Moreover, we obtain upper bounds for the number of simple cycles of a given length with a face coloring technique. Combining both, we show that there is no planar graph with more than 2.8927n simple cycles. This reduces the previous gap between the upper and lower bound for the exponential growth from 1.03 to 0.46. [ABSTRACT FROM AUTHOR]

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called "perfect phylogeny". For input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a connected subtree. The problem was introduced by Moran and Snir, who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/logk)kn4). The Moran and Snir result did not provide any nontrivial kernelization. Subsequently, a kernelization with a large polynomial bound was established. Here we give the strongest FPT results to date on this problem: (1) We show that in polynomial time, a problem kernel of size O(k2) can be obtained, and (2) We prove that the problem can be solved in linear time for fixed k. The technique used to establish the second result appears to be of general interest and applicability for bounded treewidth problems. [ABSTRACT FROM AUTHOR]

An r-component connected coloring of a graph is a coloring of the vertices so that each color class induces a subgraph having at most r connected components. The concept has been well-studied for r = 1, in the case of trees, under the rubric of convex coloring, used in modeling perfect phylogenies. Several applications in bioinformatics of connected coloring problems on general graphs are discussed, including analysis of protein-protein interaction networks and protein structure graphs, and of phylogenetic relationships modeled by splits trees. We investigate the r-Component Connected Coloring Completion (r-CCC) problem, that takes as input a partially colored graph, having k uncolored vertices, and asks whether the partial coloring can be completed to an r-component connected coloring. For r = 1 this problem is shown to be NP-hard, but fixed-parameter tractable when parameterized by the number of uncolored vertices, solvable in time O*(8k). We also show that the 1-CCC problem, parameterized (only) by the treewidth t of the graph, is fixed-parameter tractable; we show this by a method that is of independent interest. The r-CCC problem is shown to be W[1]-hard, when parameterized by the treewidth bound t, for any r ≥ 2. Our proof also shows that the problem is NP-complete for r = 2, for general graphs. [ABSTRACT FROM AUTHOR]

Several central and well-known combinatorial problems in phylogenetics and population genetics have efficient, elegant solutions when the input is complete or consists of haplotype data, but lack efficient solutions when input is either incomplete, consists of genotype data, or is for problems generalized from decision questions to optimization questions. Unfortunately, in biological applications, these harder problems arise very often. Previous research has shown that integer-linear programming can sometimes be used to solve hard problems in practice on a range of data that is realistic for current biological applications. Here, we describe a set of related integer linear programming (ILP) formulations for several additional problems, most of which are known to be NP-hard. These ILP formulations address either the issue of missing data, or solve Haplotype Inference Problems with objective functions that model more complex biological phenomena than previous formulations. These ILP formulations solve efficiently on data whose composition reflects a range of data of current biological interest. We also assess the biological quality of the ILP solutions: some of the problems, although not all, solve with excellent quality. These results give a practical way to solve instances of some central, hard biological problems, and give practical ways to assess how well certain natural objective functions reflect complex biological phenomena. Perl code to generate the ILPs (for input to CPLEX) is on the web at wwwcsif.cs.ucdavis.edu/ gusfield. [ABSTRACT FROM AUTHOR]

We introduce a generic algorithmic technique and apply it on decision and counting versions of graph coloring. Our approach is based on the following idea: either a graph has nice (from the algorithmic point of view) properties which allow a simple recursive procedure to find the solution fast, or the pathwidth of the graph is small, which in turn can be used to find the solution by dynamic programming. By making use of this technique we obtain the fastest known exact algorithms running in time O(1.7272n) for deciding if a graph is 4-colorablerunning in time O(1.6262n) and O(1.9464n) for counting the number of k-colorings for k = 3 and 4 respectively. [ABSTRACT FROM AUTHOR]

Understanding recombination is a central problem in population genetics. In this paper, we address an established problem in Computational Biology: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences [11,13,9,1,2,15]. In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated as the minimum perfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound [13], a very good lower bound in practice [15]. We prove that, like several other lower bounds [2], computing the forest bound is NP-hard. Finally, we describe an integer linear programming (ILP) formulation that computes the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing lower bounds for low quality data. [ABSTRACT FROM AUTHOR]

Given an RNA family characterized by conserved sequences and folding constraints, the problem is to search for all the instances of the RNA family in a genomic database. As seed-based heuristics have been proved very efficient to accelerate the classical homology based search methods such as BLAST, we use a similar idea for RNA structures. We present an exclusion method for RNA search allowing for possible nucleotide insertion, deletion and substitution. It is based on a partition of the RNA stem-loops into consecutive seeds and a preprocessing of the target database. This algorithm can be used to improve time efficiency of current methods, and is guaranteed to find all occurrences that contain at least one exact seed. [ABSTRACT FROM AUTHOR]

In this paper, we present an almost linear time algorithm for the problem of splitting an intensity map of radiation (represented as an integer matrix) into multiple subfields (submatrices), subject to a given maximum allowable subfield width, to minimize the total delivery error caused by the splitting. This problem arises in intensity-modulated radiation therapy (IMRT) for cancer treatments. This is the first field splitting result on minimizing the total delivery error of the splitting. Our solution models the problem as a shortest path problem on a directed layered graph, which satisfies the staircase Monge property. Consequently, the resulting algorithm runs in almost linear time and generates an optimal quality field splitting. [ABSTRACT FROM AUTHOR]

Two models for the Capacitated Multicast Routing Problem are considered, which are the Multicast k-Path Routing and the Multicast k-Tree Routing. Under these models, two improved approximation algorithms are presented, which have worst case performance ratios of 3 and (2 + ρ), respectively. Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. The two approximation algorithms improve upon the previous best ones having performance ratios of 4 and (2.4 + ρ), respectively. The designing techniques developed in the paper could be applicable to other similar networking problems. Keywords: Capacitated Multicast Routing, Approximation Algorithm, Steiner Minimum Tree, Tree Partitioning. [ABSTRACT FROM AUTHOR]

Wireless communication has many applications since its invention more than a century ago. The frequency spectrum used for communication is a scarce resource and the Frequency Assignment Problem (FAP), aiming for better utilization of the frequencies, has been extensively studied in the past 20-30 years. Because of the rapid development of new wireless applications such as digital cellular network, cellular phone, the FAP problem has become more important. In Frequency Division Multiplexing (FDM) networks, a geographic area is divided into small cellular regions or cells, usually regular hexagons in shape. Each cell contains one base station that communicates with other base stations via a high-speed wired network. Calls between any two clients (even within the same cell) must be established through base stations. When a call arrives, the nearest base station must assign a frequency from the available spectrum to the call without causing any interference with other calls. Interference may occur, which distorts the radio signals, when the same frequency is assigned to two different calls emanating from cells that are geographically close to each other. Thus the FAP problem can be viewed as a problem of multi-coloring a hexagon graph with the minimum number of colors when each vertex of the graph is associated with an integer that represents the number of calls in a cell. FAP has attracted more attention recently because of the following: a) Online analysis techniques: FAP problem is known to be NP-complete and many approximation algorithms have been proposed in the past. As frequency assignments have to be done without knowledge of future call requests and releases, online algorithms have been proposed and competitive analysis has been used to measure their performance. b) New technology and application: Wideband Code-Division Multiple-Access (W-CDMA) technology is a new technology used for the implementation of 3G cellular system. Orthogonal Variable Spreading Factor (OVSF) codes are used to satisfy requests with different data rate requirements. FAP with OVSF code trees representing the frequency spectrum becomes an important problem. [ABSTRACT FROM AUTHOR]

The scientific community is engaged in an ongoing, concerted effort to sequence the corn (also known as maize) genome. This genome is approximately 2.5 billion nucleotides long with an estimated 65-80team of university and private laboratory researchers under the auspices of NSF/USDA/DOE is working towards deciphering the majority of the sequence information including all genes, determining their order and orientation, and anchoring them to genetic/physical maps. In this talk, I will present some of the combinatorial problems that arise in this context and outline the role of graph, string and parallel algorithms in solving them. [ABSTRACT FROM AUTHOR]