Search

Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the homogeneous m -machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k -schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m -machine scheduling problem. [ABSTRACT FROM AUTHOR]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

Abstract: Neighborhoods and neighborhood sequences play important roles in several branches of pattern analysis. In earlier papers in only certain special (e.g. periodic or octagonal) sequences were investigated. In this paper we study neighborhood sequences which are either ultimately periodic or allow at every neighborhood to do nothing at no cost. We give finite procedures and descriptive theoretical criteria for certain important (e.g. metrical) properties of the sequences. Our results are valid for several types of classical neighborhood sequences and for generated distance functions (e.g. octagonal and chamfer distances) which are widely applied in digital image processing. We conclude the paper by showing how our results contribute to the theory of distance transformations. [Copyright &y& Elsevier]

Abstract: In a finite dataset consisting of positive and negative observations represented as real valued -vectors, a positive (negative) pattern is an interval in with the property that it contains sufficiently many positive (negative) observations, and sufficiently few negative (positive) ones. A pattern is spanned if it does not include properly any other interval containing the same set of observations. Although large collections of spanned patterns can provide highly accurate classification models within the framework of the Logical Analysis of Data, no efficient method for their generation is currently known. We propose in this paper, an incrementally polynomial time algorithm for the generation of all spanned patterns in a dataset, which runs in linear time in the output; the algorithm resembles closely the Blake and Quine consensus method for finding the prime implicants of Boolean functions. The efficiency of the proposed algorithm is tested on various publicly available datasets. In the last part of the paper, we present the results of a series of computational experiments which show the high degree of robustness of spanned patterns. [Copyright &y& Elsevier]

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]

Abstract: A finite Sturmian word is a balanced word over the binary alphabet , that is, for all subwords and of of equal length, , where and denote the number of occurrences of the letter in and , respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity. [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [Copyright &y& Elsevier]

Abstract: It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough. We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve. [Copyright &y& Elsevier]

Abstract: The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.’s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model. [Copyright &y& Elsevier]

Abstract: Given a simple polygon with two vertices and , the three-guard problem asks whether three guards can move from to such that the first and third guards are separately on two boundary chains of from to and the second guard is always kept to be visible from two other guards inside . It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from to and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in time, and if so generate a walk in time, where denotes the number of vertices of and the size of the optimal walk. This improves upon the previous time bounds and , respectively. Moreover, our results can be used to solve other more sophisticated geometric problems. [Copyright &y& Elsevier]

Abstract: Imposing constraints is a way to incorporate information into the sequence alignment procedure. In this paper, a general model for constrained alignment is proposed so that analyses admitted are more flexible and that different pattern definitions can be treated in a simple unified way. We give a polynomial time algorithm for pairwise constrained alignment for the generalized formulation, and prove the inapproximability of the problem when the number of sequences can be arbitrary. In addition, previous works deal only with the case that the patterns in the constraint have to occur in the output alignment in the same order as that specified by the input. It is of both theoretical and practical interest to investigate the case when the order is no longer limited. We show that the problem is not approximable even when the number of sequences is two. We also give the NPO-completeness results for the problems with bounds imposed on the objective function value. [Copyright &y& Elsevier]

Abstract: Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an -geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma [http://magma.maths.usyd.edu.au] and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups. [Copyright &y& Elsevier]

Abstract: A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs. [Copyright &y& Elsevier]

Abstract: For the earliest arrival flow problem one is given a network with capacities and transit times on its arcs , together with a source and a sink vertex . The objective is to send flow from s to t that moves through the network over time, such that for each time the maximum possible amount of flow up to this time reaches t. If, for each , this flow is a maximum flow for time horizon , then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time depends on the flow on this particular arc at that time . For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each , need only -times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on ; furthermore, we present a constant factor approximation algorithm for this problem. [Copyright &y& Elsevier]

Abstract: This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In our problem, channels assigned to adjacent vertices must be at least 2 apart, while channels assigned to vertices at distance 2 must be different. An exact linear time algorithm is provided for the class of threshold graphs. For matrogenic and matroidal graphs approximate algorithms are given. Consequently, previously known results concerning subclasses of cographs, split graphs and graphs with diameter 2 are improved. [Copyright &y& Elsevier]

Abstract: Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class , where for each graph G in , the removal of a set of at most k vertices from G results in a graph in the base graph class . (If is the class of edgeless graphs, is the class of graphs with bounded vertex cover.) When is a minor-closed class such that each graph in has bounded maximum degree, and all obstructions of (minor-minimal graphs outside ) are connected, we obtain an recognition algorithm for , where g and f are constants (modest and quantified) depending on the class . If is the class of graphs with maximum degree bounded by (not closed under minors), we can still obtain a running time of for recognition of graphs in . Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for is , where t is a bound on the size of obstructions for . A trivial corollary of this result is an upper bound of on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. [Copyright &y& Elsevier]

Abstract: Given a discrete eight-connected curve, it can be represented by discrete eight connected segments. In this paper, we try to determine the minimal number of necessary discrete segments. This problem is known as the min DSS problem. We propose to use a generic curve representation by discrete tangents, called a tangential cover which can be computed in linear time. We introduce a series of criteria each having a linear-time complexity to progressively solve the min DSS problem. This results in an optimal algorithm both from the point of view of optimization and of complexity, outperforming the previous quadratic bound. [Copyright &y& Elsevier]

Abstract: Fuzzy segmentation is a technique that assigns to each element in an image (which may have been corrupted by noise and/or shading) a grade of membership in an object (which is believed to be contained in the image). In an earlier work, the first two authors extended this concept by presenting and illustrating an algorithm which simultaneously assigns to each element in an image a grade of membership in each one of a number of objects (which are believed to be contained in the image). In this paper, we prove the existence of such a fuzzy segmentation that is uniquely specified by a desirable mathematical property, show further examples of its use in medical imaging, and illustrate that on several biomedical examples a new implementation of the algorithm that produces the segmentation is approximately seven times faster than the previously used implementation. We also compare our method with two recently published related methods. [Copyright &y& Elsevier]

Abstract: In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced . For a graph on vertices and edges, both our cograph recognition and cotree construction algorithms run in time and require processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal -time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal -time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced ) whenever our algorithms decide that the input graphs are not cographs. [Copyright &y& Elsevier]

Abstract: Probe interval graphs (PIGs) are used as a generalization of interval graphs in physical mapping of DNA. is a probe interval graph (PIG) with respect to a partition of V if vertices of G correspond to intervals on a real line and two vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is in P; vertices belonging to P are called probes and vertices belonging to N are called non-probes. One common approach to studying the structure of a new family of graphs is to determine if there is a concise family of forbidden induced subgraphs. It has been shown that there are two forbidden induced subgraphs that characterize tree PIGs. In this paper we show that having a concise forbidden induced subgraph characterization does not extend to 2-tree PIGs; in particular, we show that there are at least 62 minimal forbidden induced subgraphs for 2-tree PIGs. [Copyright &y& Elsevier]

Abstract: Factoring Boolean functions is one of the basic operations in algorithmic logic synthesis. Current algorithms for factoring Boolean functions are based on some kind of division (Boolean or algebraic). In this paper, we present an algorithm for factoring that uses graph partitioning rather than division. Our algorithm is recursive and operates on the function and on its dual, to obtain the better factored form. As a special class, which appears in the lower levels of the factoring process, we handle read-once functions separately, as a special purpose subroutine which is known to be optimal. Since obtaining an optimal (shortest length) factorization for an arbitrary Boolean function is an NP-hard problem, all practical algorithms for factoring are heuristic and provide a correct, logically equivalent formula, but not necessarily a minimal length solution. Our method has been implemented in the SIS environment, and an empirical evaluation indicates that we usually get significantly better factorizations than algebraic factoring and are quite competitive with Boolean factoring but with lower computation costs. [Copyright &y& Elsevier]

Abstract: We consider the problem of numerical representations of PQI interval orders. A preference structure on a finite set A with three relations standing for “strict preference”, “weak preference” and “indifference”, respectively, is defined as a PQI interval order iff there exists a representation of each element of A by an interval in such a way that, P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non-empty intersection (Q modelling the hesitation between P and I). Only recently, necessary and sufficient conditions for a PQI preference structure to be identified as a PQI interval order have been established. In this paper, we are interested in the problem of constructing a numerical representation of a PQI interval order and possibly a minimal one. We present two algorithms, the first one in aimed to determine a general numerical representation, and the second one, in , aimed to minimise such a representation. [Copyright &y& Elsevier]

Abstract: Many NP-complete problems on planar graphs are “fixed-parameter tractable:” Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time . Here, is some constant depending on the graph problem to be solved, is the number of graph vertices, and is the problem parameter (for VERTEX COVER this is the size of the vertex cover). In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory. [Copyright &y& Elsevier]

Let G=(V,E,w) be an undirected graph with positive edge lengths and S⊂V a set of k specified sources. The k-source maximum eccentricity spanning tree is a spanning tree T minimizing the maximum distance from a source to a vertex, i.e., maxs∈S {maxv∈V{dT(s,v)}}, where dT(s,v) is the length of the path between s and v in T. In this paper, we propose an O(|V|2 log |V|+|V| |E|) time algorithm, which improves the previous result on the problem. [Copyright &y& Elsevier]

In this paper, we present a repair-based linear-time algorithm to solve a version of the Sports League Scheduling Problem (SLSP) where the number T of teams is such that (T-1) mod 3≠0. Starting with a conflicting schedule with particular properties, the algorithm removes iteratively the conflicts by exchanging matches. The properties of the initial schedule make it possible to take the optimal exchange at each iteration, leading to a linear-time algorithm. This algorithm can find thus valid schedules for several thousands of teams in less than 1 min. It is still an open question whether the SLSP can be solved efficiently when (T-1) mod 3=0. [Copyright &y& Elsevier]

We study the following Constrained Bipartite Edge Coloring problem: We are given a bipartite graph G=(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three. Two special cases of the problem have been previously considered and tight upper and ower bounds on the optimal number of colors were proved. The upper bounds led to 3/2-approximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where max{l,c}=ω(ln n). Our techniques are motivated by recent works on the Circular Arc Coloring problem and are essentially different and simpler than the existing ones. [Copyright &y& Elsevier]

In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247m|F|), where m is the number of clauses in F, and |F| is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695k+|F|) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. [Copyright &y& Elsevier]

In this paper, we present an integer programming formulation of the prize collecting Steiner problem in graphs (PCSPG) and describe an algorithm to obtain lower bounds for the problem. The algorithm is based on polyhedral cutting planes and is initiated with tests that attempt to reduce the size of the input graph. Computational experiments were carried out to evaluate the strength of the formulation through its linear programming relaxation. On 96 out of the 114 instances tested, integer solutions were found (thus generating optimal PCSPG solutions). [Copyright &y& Elsevier]

In this paper we characterize the class of plane graphs that can be embedded on the two-dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configuration or generates an embedding with at most one bend on each edge. [Copyright &y& Elsevier]

In this paper the classical stable roommates problem is generalized to situations when the two partners in a pair perform different roles. We propose an efficient algorithm to decide the existence of a stable matching in this problem. [Copyright &y& Elsevier]

The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The input to the problem consists of a series of modifications to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold. In this paper, we solve the dynamic recognition problem for the class of cographs and some of its subclasses. Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition. We give the first fully dynamic algorithm for maintaining the modular decomposition tree of a cograph. We thereby obtain fully dynamic algorithms for the recognition of cographs, threshold graphs, and trivially perfect graphs. All these algorithms work in constant time per edge modification and O(d) time per d-degree vertex modification. [Copyright &y& Elsevier]

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most √ of 2 times that of the shortest watchman route. The best known algorithm for computing the shortest watchman route through s takes O(n4) time. In addition, it is too complicated to be suitable in practice. Moreover, our approximation scheme can be applied to the zookeeper’s problem, which is a variant of the watchman route problem. [Copyright &y& Elsevier]