The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this paper, we study a colouring problem motivated by a practical frequency assignment problem and up to our best knowledge new. In wireless networks, a node interferes with the other nodes the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph G where the weights on the edges represent...
In this paper we initiate a systematic study of a problem that has the flavor of two classical problems, namely Coloring and Domination, from the perspective of algorithms and complexity. A dominator coloring of a graph G is an assignment of colors to the vertices of G such that it is a proper coloring and every vertex dominates all the vertices of at least one color class. The minimum number of colors...
The longest previous factor (LPF) problem is defined for traditional strings exclusively from the constant alphabet Σ. A parameterized string (p-string) is a sophisticated string composed of symbols from a constant alphabet Σ and a parameter alphabet Π. We generalize the LPF problem to the parameterized longest previous factor (pLPF) problem defined for p-strings. Subsequently, we present a linear...
The challenge of direct parameterized suffix sorting (p-suffix sorting) for a parameterized string (p-string) is the dynamic nature of parameterized suffixes (p-suffixes). In this work, we propose transformative approaches to direct p-suffix sorting by generating and sorting lexicographically numeric fingerprints and arithmetic codes that correspond to individual p-suffixes. Our algorithm to p-suffix...
Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine-Wilf theorem shows the existence of a bound L = L(h,p,q) such that if a partial word of length at least L with h holes has periods p and q, then it has period $\gcd(p,q)$ . In this paper, we associate a graph with each p- and q-periodic word, and study two types of...
We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency...
The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from O*(1.76k) to O*(1.62k). In detail, we can show that we can always...
Consider the following reversible cascade on the Erdős-Rényi random graph G(n,p). In round zero, a set of vertices, called the seeds, are active. For a given ρ ∈ ( 0,1 ], a non-isolated vertex is activated (resp., deactivated) in round t ∈ ℤ + if the fraction f of its neighboring vertices that were active in round t − 1 satisfies f ≥ ρ (resp., f < ρ). An irreversible cascade is defined similarly...
We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)—a problem raised in Fellows’ thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami’s conjecture—which is still open—as the two were considered...
A checking test for a monotone read-once function f depending essentially on all its n variables is a set of vectors M distinguishing f from all other monotone read-once functions of the same variables. We describe an inductive procedure for obtaining individual lower and upper bounds on the minimal number of vectors T(f) in a checking test for any function f. The task of deriving the exact value...
The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of H in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each Cℓ with ℓ ≥ 3 is NP-complete. In this paper, we...
Greedy methods for solving set cover problems provide a guarantee on how close the solution is to optimal. Consequently they have been widely explored to solve set cover problems arising in the construction of various combinatorial arrays, such as covering arrays and hash families. In these applications, however, a naive set cover formulation lists a number of candidate sets that is exponential in...
A 2-layer drawing represents a bipartite graph so that the vertices of each partition set are points of a distinct horizontal line (called a layer) and the edges are straight-line segments. In this paper we study 2-layer drawings where all edge crossings form right angles. We characterize which graphs admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time...
Given a set of red and blue points, an orthogeodesic alternating path is a path such that each edge is a geodesic orthogonal chain connecting points of different colour and no two edges cross. We consider the problem of deciding whether there exists a Hamiltonian orthogeodesic alternating path, i.e., an orthogeodesic alternating path visiting all points. We provide an O(n log2n)-time algorithm...
A binary string B of length n = kt is a k-ary Dyck word if it contains t copies of 1, and the number of 0s in every prefix of B is at most k−1 times the number of 1s. We provide two loopless algorithms for generating k-ary Dyck words in cool-lex order: (1) The first requires two index variables and assumes k is a constant; (2) The second requires t index variables and works for any k. We...
In this paper we introduce two efficient priority queues. For both, insert requires O(1) amortized time and extract-min $O(\lg n)$ worst-case time including at most $\lg n + O(1)$ element comparisons, where n is the number of elements stored. One priority queue is based on a weak heap (array-based) and the other on a weak queue (pointer-based). In both, the main idea is to temporarily store...
We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element x in worst-case $O(\lg(\min\{w_x, q_x\}+2))$ time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access...
We prove that the number of monomer-dimer tilings of an n×n square grid, with m < n monomers in which no four tiles meet at any point is m2m + (m + 1)2m + 1, when m and n have the same parity. In addition, we present a new proof of the result that there are n2n − 1 such tilings with n monomers, which divides the tilings into n classes of size...
Let dq(n,k) be the maximum possible minimum Hamming distance of a linear [n,k] code over . Tables of best known linear codes exist for all fields up to q = 9. In this paper, linear codes over are constructed for k up to 6. The codes constructed are from the class of quasi-cyclic codes. In addition, the minimum distance of...
An acyclic coloring of a graph G is a coloring of the vertices of G, where no two adjacent vertices of G receive the same color and no cycle of G is bichromatic. An acyclic k-coloring of G is an acyclic coloring of G using at most k colors. In this paper we prove that any triangulated plane graph G with n vertices has a subdivision that is acyclically 4-colorable, where the number of division vertices...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.