Search

In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n − k) time for each, while our algorithm generates such trees in O(1) time for each in worst case. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the problem of generating all triangulations of plane graphs. We give an algorithm for generating all triangulations of a triconnected plane graph G of n vertices. Our algorithm establishes a tree structure among the triangulations of G, called the ˵tree of triangulations,″ and generates each triangulation of G in O(1) time. The algorithm uses O(n) space and generates all triangulations of G without duplications. To the best of our knowledge, our algorithm is the first algorithm for generating all triangulations of a triconnected plane graph; although there exist algorithms for generating triangulated graphs with certain properties. Our algorithm for generating all triangulations of a triconnected plane graph needs to find all triangulations of a convex polygon. We give an algorithm to generate all triangulations of a convex polygon P of n vertices in time O(1) per triangulation, where the vertices of P are numbered. Our algorithm for generating all triangulations of a convex polygon also improves previous results; existing algorithms need to generate all triangulations of convex polygons of less than n vertices before generating the triangulations of a convex polygon of n vertices. Finally, we give an algorithm for generating all triangulations of a convex polygon P of n vertices in time O(n2) per triangulation, where vertices of P are not numbered. [ABSTRACT FROM AUTHOR]

In this paper we give a coding scheme for plane triangulations. The coding scheme is very simple, and needs only 6n bits for each plane triangulation with n vertices. Also with additional o(n) bits it supports adjacency, degree and clockwise neighbour queries in constant time. Our scheme is based on a realizer of a plane triangulation. The best known algorithm needs only 4.35n + o(n) bits for each plane triangulation, however, within o(n) bits it needs to store a complete list of all possible triangulations having at most (logn)/4 nodes, while our algorithm is simple and does not need such a list. The second best known algorithm needs 2m + (5 + 1/k)n + o(m + n) bits for each (general) plane graph with m edges and 7n + o(n) bits for each plane triangulation, while our algorithm needs only 6n + o(n) bits for each plane triangulation. [ABSTRACT FROM AUTHOR]

Given an edge weighted tree T and two non-negative real numbers dmin and dmax, a pairwise compatibility graph (PCG) of T is a graph G = (V,E), where each vertex u ∈ V corresponds to a leaf u of T and an edge (u, v) ∈ E if and only if dmin ≤ distance(u, v) ≤ dmax in T. In this paper we give some properties of these graphs. We establish a relationship between pairwise compatibility graphs and chordal graphs. We show that all chordless cycles and single chord cycles are pairwise compatibility graphs. We also provide a linear-time algorithm for constructing trees that can generate graphs having cycles as their maximal biconnected subgraphs as PCGs. The techniques that we used to identify various types of pairwise compatibility graphs are quite generic and may be useful to discover other properties of these graphs. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the graph bandwidth parameter: for a graph G and an integer $k\leq\text{diam}(G)$, the k-level bandwidth Bk(G) of G is defined by $B^k(G)=\min_\gamma \max\{\gamma(x)-\gamma(y)-d(x,y)+1: x,y\in V(G),d(x,y)\leq k\},$ the minimum being taken among all proper numberings γ of the vertices of G. We present general bounds on Bk(G) along with more specific results for k = 2 and the exact value for $k=\text{diam}(G)$. We also exhibit relations between the k-level bandwidth and radio k-labelings of graphs from which we derive a upper bound for the radio number of an arbitrary graph. [ABSTRACT FROM AUTHOR]

The competitive ratio is the most common metric in online algorithm analysis. Unfortunately, it produces pessimistic measures and often fails to distinguish between paging algorithms that have vastly differing performance in practice. An apparent reason for this is that the model does not take into account the locality of reference evidenced by actual input sequences. Therefore many alternative measures have been proposed to overcome the observed shortcomings of competitive analysis in the context of paging algorithms. While a definitive answer to all the concerns has yet to be found, clear progress has been made in identifying specific flaws and possible fixes for them. In this paper we consider two previously proposed models of locality of reference and observe that even if we restrict the input to sequences with high locality of reference in them the performance of every on-line algorithm in terms of the competitive ratio does not improve. Then we prove that locality of reference is useful under some other cost models, which suggests that a new model combining aspects of both proposed models can be preferable. We also propose a new model for locality of reference and prove that the randomized marking algorithm has better fault rate on sequences with high locality of reference. Finally we generalize the existing models to several variants of the caching problem. [ABSTRACT FROM AUTHOR]

In this paper we give a simple algorithm to generate all connected rooted plane graphs with at most m edges. A "rooted" plane graph is a plane graph with one designated (directed) edge on the outer face. The algorithm uses O(m) space and generates such graphs in O(1) time per graph on average without duplications. The algorithm does not output the entire graph but the difference from the previous graph. By modifying the algorithm we can generate all connected (non-rooted) plane graphs with at most m edges in O(m3) time per graph. [ABSTRACT FROM AUTHOR]

We consider inverse chromatic number problems in interval graphs having the following form: we are given an integer K and an interval graph G = (V,E), associated with n = V intervals Ii = ]ai,bi[ (1 ≤ i ≤ n), each having a specified length s(Ii) = bi − ai, a (preferred) starting time ai and a completion time bi. The intervals are to be newly positioned with the least possible discrepancies from the original positions in such a way that the related interval graph can be colorable with at most K colors. We propose a model involving this problem called inverse booking problem.We show that inverse booking problems are hard to approximate within O(n1 − ε), ε> 0 in the general case with no constraints on lengths of intervals, even though a ratio of n can be achieved by using a result of [13]. This result answers a question recently formulated in [12] about the approximation behavior of the unweighted case of single machine just-in-time scheduling problem with earliness and tardiness costs. Moreover, this result holds for some restrictive cases. [ABSTRACT FROM AUTHOR]

The problem of finding the minimum r-star cover of orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomial tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, their algorithm is not practical as it has $\tilde{O}(n^{17})$ time complexity, where $\tilde{O}()$ hides a polylogarithmic factor. Herein, we present a linear-time 3-approximation algorithm based upon the novel partition of a polygon into so-called [w]-star-shaped orthogonal polygons. [ABSTRACT FROM AUTHOR]

In this paper, our objective is to locate a position of a guard on the convex hull of a simple polygon P, such that, the farthest point on the boundary of the polygon from the location of the guard, avoiding the interior region of the polygon P, is minimum among all possible locations of the guard on the convex hull. In other words, we try to identify the possible position of guard on the boundary of convex hull such that the maximum distance required to reach a trouble point on the boundary of polygon P avoiding the interior region of P is minimized. The time complexity of our algorithm is O(n) where n is the number of vertices of P. [ABSTRACT FROM AUTHOR]

Finding a maximum acyclic subgraph is on the list of problems that seem to be hard to tackle from a parameterized perspective. We develop two quite efficient algorithms (one is exact, the other parameterized) for (1,n)-graphs, a class containing cubic graphs. The running times are $\mathcal{O}^*(1.1871^m)$ and $\mathcal{O}^*(1.212^k)$, respectively, determined by an amortized analysis via a non-standard measure. [ABSTRACT FROM AUTHOR]

A packet-switched network is universally stable if, for any greedy protocol and any adversary of injection rate less than 1, the number of packets in the network remains bounded at all times. A natural question that arises is whether there is a fast way to detect if a network is universally stable based on the network's structure. In this work, we study this question in the context of Adversarial Queueing Theory which assumes that an adversary controls the locations and rates of packet injections and determines packet paths. Within this framework, we present optimal algorithms for detecting the universal stability (packet paths do not contain repeated edges but may contain repeated vertices) and the simple-path universal stability (paths contain neither repeated vertices nor repeated edges) of a network. Additionally, we describe an algorithm which decides in constant time whether the addition of a link in a universally stable network leads it to instability; such an algorithm could be useful in detecting intrusion attacks. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E), we say that a vertex subset S ⊆ V covers a vertex v ∈ V if the edge-connectivity between S and v is at least a given integer k, and also say that S covers an edge vw ∈ E if v and w are covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, r players each select p vertices, and obtain a profit that is the total weight of covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the price of greed, which indicates the ratio of the total profit of cooperating players to that of selfish players, is tightly bounded by min { r,p}. Also when k = 2, we obtain tight bounds for vertex-unweighted trees. [ABSTRACT FROM AUTHOR]

The class doughnut graphs is a subclass of 5-connected planar graphs. In a planar embedding of a doughnut graph of n vertices there are two vertex-disjoint faces each having exactly n/4 vertices and each of all the other faces has exactly three vertices. Recently the class of doughnut graphs is introduced to show that a graph in this class admits a straight-line grid drawing with linear area and hence any spanning subgraph of a doughnut graph also admits a straight-line grid drawing with linear area. But recognition of a spanning subgraph of a doughnut graph is a non-trivial problem, since recognition of a spanning subgraph of a given graph is an NP-complete problem in general. In this paper, we establish a necessary and sufficient condition for a 4-connected planar graph G to be a spanning subgraph of a doughnut graph. We also give a linear-time algorithm to augment a 4-connected planar graph G to a doughnut graph if G satisfies the necessary and sufficient condition. [ABSTRACT FROM AUTHOR]

In an orthogonal projection of a convex polyhedron P the visibility ratio of a face f (similarly of an edge e) is the ratio of orthogonally projected area of f (length of e) and its actual area (length). In this paper we give algorithms for nice projections of P such that the minimum visibility ratio over all visible faces (over all visible edges) is maximized. [ABSTRACT FROM AUTHOR]

A straight-line drawing of a plane graph G is a drawing of G where each vertex is drawn as a point and each edge is drawn as a straight-line segment without edge crossings. A proximity drawing Γ of a plane graph G is a straight-line drawing of G with the additional geometric constraint that two vertices of G are adjacent if and only if no other vertex of G is drawn in Γ within a "proximity region" of these two vertices in Γ. Depending upon how the proximity region is defined, a given plane graph G may or may not admit a proximity drawing. In one class of proximity drawings, known as β-drawings, the proximity region is defined in terms of a parameter β, where β ∈ [0, ∞ ). A plane graph G is β-drawable if G admits a β-drawing. A sufficient condition for a biconnected 2-outerplane graph G to have a β-drawing is known. However, the known algorithm for testing the sufficient condition takes time O(n2). In this paper, we give a linear-time algorithm to test whether a biconnected 2-outerplane graph G satisfies the known sufficient condition or not. This consequently leads to a linear algorithm for β-drawing of a wide subclass of biconnected 2-outerplane graphs. [ABSTRACT FROM AUTHOR]

Voronoi diagrams for a fix set of generators are considered with varying Lp norm. For a generator q in the set, the absolute neighbor of q is defined to be the intersection of all Voronoi regions of q by Lp norm(p = 1, 2..., ∞). Since the shape of Voronoi region is dependent on the norm used, the collection of absolute neighbors for the set does not always cover the whole space. In this paper, we construct absolute neighbors and computed the ratio, called cover ratio, of the volume covered by all absolute neighbors to that of the whole space for some sets of generators by computational experiments. Computational experiments show that the cover ratio is higher when a configuration of grid points is used as a set of generators than when a set of random generators is used. Moreover, we theoretically show that the absolute neighbors for square configuration and for face-centered configuration cover the whole space. We also discuss an application of absolute neighbors to constructing an index structure of the whole space for efficient retrieval. [ABSTRACT FROM AUTHOR]

In a planar straight-line drawing of a tree T on k layers, each vertex is placed on one of k horizontal lines called layers and each edge is drawn as a straight-line segment. A planar straight-line drawing of a rooted tree T on k layers is called an upward drawing of T on k layers if, for each vertex u of T, no child of u is placed on a layer vertically above the layer on which u has been placed. For a tree T having pathwidth h, a linear-time algorithm is known that produces a planar straight-line drawing of T on ⌈3h/2⌉ layers. A necessary condition characterizing trees that admit planar straight-line drawings on k layers for a given value of k is also known. However, none of the known algorithms focuses on drawing a tree on the minimum number of layers. Moreover, although an upward drawing is the most useful visualization of a rooted tree, the known algorithms for drawing trees on k layers do not focus on upward drawings. In this paper, we give a linear-time algorithm to compute the minimum number of layers required for an upward drawing of a given rooted tree T. If T is not a rooted tree, then we can select a vertex u of T in linear time such that an upward drawing of T rooted at u would require the minimum number of layers among all other upward drawings of T rooted at the vertices other than u. We also give a linear-time algorithm to obtain an upward drawing of a rooted tree T on the minimum number of layers. [ABSTRACT FROM AUTHOR]

This paper deals with the Circular Pattern Matching Problem (CPM). In CPM, we are interested in pattern matching between the text $\mathcal T$ and the circular pattern $\mathcal C(\mathcal P)$ of a given pattern $\mathcal P = \mathcal P_1 \ldots \mathcal P_m$. The circular pattern $\mathcal C(\mathcal P)$ is formed by concatenating $\mathcal P_1$ to the right of $\mathcal P_m$. We can view $\mathcal C(\mathcal P)$ as a set of m patterns starting at positions j ∈ [1..m] and wrapping around the end and if any of these patterns matches $\mathcal T$, we find a match for $\mathcal C(\mathcal P)$. In this paper, we present two efficient data structures to index circular patterns. This problem has applications in pattern matching in geometric and astronomical data as well as in computer graphics and bioinformatics. [ABSTRACT FROM AUTHOR]

In this paper, a fast algorithm is proposed to calculate kth power of an n×n Boolean matrix that requires O(kn3p) addition operations, where p is the probability that an entry of the matrix is 1. The algorithm generates a single set of inference rules at the beginning. It then selects entries (specified by the same inference rule) from any matrix Ak − 1 and adds them up for calculating corresponding entries of Ak. No multiplication operation is required. A modification of the proposed algorithm can compute the diameter of any graph and for a massive random graph, it requires only O(n2(1-p)E[q]) operations, where q is the number of attempts required to find the first occurrence of 1 in a column in a linear search. The performance comparisons say that the proposed algorithms outperform the existing ones. [ABSTRACT FROM AUTHOR]

A graph G = (V,E) is said to be an intersection graph if and only if there is a set of objects such that each vertex v in V corresponds to an object Ov and {u,v} ∈ E if and only if Ov and Ou have a nonempty intersection. Interval graphs are typical intersection graph class, and widely investigated since they have simple structures and many hard problems become easy on the graphs. In this paper, we survey known results and investigate (unit) grid intersection graphs, which is one of natural generalized interval graphs. We show that the graph class has so rich structure that some typical problems are still hard on the graph class. [ABSTRACT FROM AUTHOR]

This paper studies a vertex domination problem in dynamic networks, which allows dynamic change of the set of vertices, the set of edges, and the set of weights. In particular, we will examine the following two theoretical issues arising in designing an adaptive vertex domination scheme for such networks: 1) How can we transfer a given configuration to a dominating configuration while keeping that any intermediate configuration is safe? 2) How can we reduce the computational complexity of the vertex domination problem by allowing defections in the domination? [ABSTRACT FROM AUTHOR]

We compare the theory and practice of online algorithms, and show that in certain instances there is a large gap between the predictions from theory and observed practice. In particular, the competitive ratio which is the main technique for analysis of online algorithms is known to produce unrealistic measures of performance in certain settings. Motivated by this we examine first the case of paging. We present a study of the reasons behind this apparent failure of the theoretical model. We then show that a new measure derived from first principles and introduced by [Angelopoulos, Dorrigiv and López-Ortiz, SODA 2007] better corresponds to observed practice. Using these ideas, we derive a new framework termed the cooperative ratio that generalizes to all other online analysis settings and illustrate with examples in list update. [ABSTRACT FROM AUTHOR]

A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such measures has been proposed in the recent past: number of reversals, number of breakpoints, number of common or conserved intervals, SAD etc. In their initial definitions, all these measures suppose that genomes contain no duplicates. However, we now know that genes can be duplicated within the same genome. One possible approach to overcome this difficulty is to establish a one-to-one correspondence (i.e. a matching) between genes of both genomes, where the correspondence is chosen in order to optimize the studied measure. Then, after a gene relabeling according to this matching and a deletion of the unmatched signed genes, two genomes without duplicates are obtained and the measure can be computed. In this paper, we are interested in three measures (number of breakpoints, number of common intervals and number of conserved intervals) and three models of matching (exemplar model, maximum matching model and non maximum matching model). We prove that, for each model and each measure, computing a matching between two genomes that optimizes the measure is APX-Hard. We show that this result remains true even for two genomes G1 and G2 such that G1 contains no duplicates and no gene of G2 appears more than twice. Therefore, our results extend those of [5,6,8]. Finally, we propose a 4-approximation algorithm for a measure closely related to the number of breakpoints, the number of adjacencies, under the maximum matching model, in the case where genomes contain the same number of duplications of each gene. [ABSTRACT FROM AUTHOR]

A rectangular drawing is a plane drawing in which every face is a rectangle. In this paper we give a simple encoding scheme for rectangular drawings. Given a rectangular drawing R with maximum degree 3, our scheme encodes R with $\frac{5}{3}m + o(n)$ bits for each n-vertex rectangular drawing R, where m is the number of edges of R, and supports a rich set of queries, including adjacency and degree queries on the faces, in constant time. [ABSTRACT FROM AUTHOR]

The airlines in the real world form small-world network. This implies that they are constructed with an ad hoc strategy. The small-world network is not so bad from the viewpoints of customers and managers. The customers can fly to any destination through a few airline hubs, and the number of airlines is not so many comparing to the number of airports. However, clearly, it is not the best solution in either viewpoint since there is a trade off. In this paper, one of the extreme cases, which is the standpoint of the manager, is considered; we assume that customers are silent and they never complain even if they are required to transit many times. This assumption is appropriate for some transportation service and packet communication. Under this assumption, the airline problem is to construct the least cost connected network for given distribution of the populations of cities with no a priori connection. First, we show an efficient algorithm that produces a good network which is minimized the number of vacant seats. The resultant network contains at most n connections (or edges), where n is the number of cities. Next we aim to minimize not only the number of vacant seats, but also the number of airline connections. The connected network with the least number of edges is a tree which has exactly n − 1 connections. However, the problem to construct a tree airline network with the minimum number of vacant seats is ${\cal NP}$-complete. We also propose efficient approximation algorithms to construct a tree airline network with the minimum number of vacant seats. [ABSTRACT FROM AUTHOR]