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 the context of scheduling and timetabling, we study a challenging combinatorial problem which is interesting from both a practical and a theoretical point of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disturbances, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled...
The Longest Common Subsequence (LCS) of two strings A and B is a well studied problem having a wide range of applications. When each symbol of the input strings is assigned a positive weight the problem becomes the Heaviest Common Subsequence (HCS) problem. In this paper we consider a different version of weighted LCS on Position Weight Matrices (PWM). The Position Weight Matrix was introduced as...
Balanceable clutters are clutters whose bipartite representation contains no odd wheel and no odd 3-path configuration as induced subgraph (this is Truemper’s characterization of balanceable matrices). In this paper we study a proper subclass of balanceable clutters called quasi-graphical defined by forbidding one-sided even wheels and one-sided even 3-path configurations. We characterize Mengerian...
We present an improved upper bound of $O(d^{1+\frac{1}{m-1}})$ for the $(2,\mathcal{F})$ -subgraph chromatic number $\chi_{2,\mathcal{F}}(G)$ of any graph G of maximum degree d. Here, m denotes the minimum number of edges in any member of . This bound is tight up to a (logd)1/(m − 1) multiplicative factor and improves the previous bound presented in [1]. We also...
A graph G = (V,E) is a 3-leaf power iff there exists a tree T the leaf set of which is V and such that (u,v) ∈ E iff u and v are at distance at most 3 in T. The 3-leaf power edge modification problems, i.e. edition (also known as the Closest 3-Leaf Power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, a polynomial kernel was known for none...
We study the weighted generalization of the edge coloring problem where the goal is to minimize the sum of the weights of the heaviest edges in the color classes. In particular, we deal with the approximability of this problem on bipartite graphs and trees. We first improve the best known approximation ratios for bipartite graphs of maximum degree . For trees we present a polynomial...
We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P6-free graphs. Recent results of Hoàng et al. imply that this problem...
We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, i.e., whether it can be partitioned into connected parts of order α1,α2,...,αk for every α1,α2,...,α...
The Feedback Vertex Set problem asks whether a graph contains q vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G of cliquewidth cw and a cw-expression...
R. Häggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K6n,6n. In [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into certain families of...
A circuit in a simple undirected graph G = (V,E) is a sequence of vertices {v1,v2,...,vk + 1} such that v1 = vk + 1 and {vi,vi + i} ∈ E for i = 1,...,k. A circuit C is said to be edge-simple if no edge of G is used twice in C. In this article we...
In this paper we address the problem of designing O(n) space representations for permutation and interval graphs that provide the neighborhood of any vertex in O(d) time, where d is its degree. To that purpose, we introduce a new parameter, called linearity, that would solve the problem if bounded for the two classes. Surprisingly, we show that it is not. Nevertheless, we design representations with...
We present efficient algorithms for storing past segments of a text. They are computed using two previously computed read-only arrays (SUF and LCP) composing the Suffix Array of the text. They compute the maximal length of the previous factor (subword) occurring at each position of the text in a table called LPF. This notion is central both in many conservative text compression techniques and in the...
This paper examines the distances between vertices in a rooted k-tree, for a fixed k, by exhibiting a correspondence with a variety of trees that can be specified in terms of combinatorial specifications. Studying these trees via generating functions, we show a Rayleigh limiting distribution for expected distances between pairs of vertices in a random k-tree: in a k-tree on n vertices, the proportion...
An n-bit (cyclic) Gray code is a (cyclic) sequence of all n-bit strings such that consecutive strings differ in a single bit. We describe an algorithm which for every positive integer n constructs an n-bit cyclic Gray code whose graph of transitions is the d-dimensional hypercube Qd if n = 2d, or a subgraph of Qd...
Embedded trees are labelled rooted trees, where the root has zero label and where the labels of adjacent vertices differ by ±1. Recently it was proved by Chassaing and Schaeffer, and Janson and Marckert that the distribution of the maximum and minimum label are closely related to the support of the density of the integrated superbrownian excursion (ISE). The purpose of this paper is make this probabilistic...
We analyze special random network models – so-called thickened trees – which are constructed by random trees where the nodes are replaced by local clusters. These objects serve as models for random real world networks. It is shown that under a symmetry condition for the cluster sets a local-global principle for the degree distribution holds: the degrees given locally through the choice of the cluster...
Polar graphs generalise bipartite, cobipartite, split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP-complete problem. Here we show that...
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.