BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Irena Rusu

Irena Rusu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath.COArtificial IntelligenceComputational Engineering, Finance, and ScienceQuantitative Methods

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Stick graphs: examples and counter-examples

Grid intersection graphs are the intersection graphs of vertical and horizontal segments in the plane. When the bottom and respectively left endpoints of the vertical and horizontals segments belong to a line with negative slope, the graph is called a Stick graph. Very few results exist on Stick graphs: only small classes of Stick graphs have been identified; recognizing Stick graphs is an open problem; and even building examples of graphs that are not Stick graphs is quite tricky. In this paper, we first prove that the complements of circle graphs and of circular arc graphs are Stick graphs. Then, we propose two certificates allowing to decide that a graph is not a Stick graph, and use them to build new examples of non-Stick graphs. It turns out that these examples of non-Stick graphs, as well as all those from literature, have long holes. We thus also investigate the place of chordal grid intersection graphs in the hierarchy of classes built around Stick graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sorting Permutations with Fixed Pinnacle Set

We give a positive answer to a question raised by Davis et al. ({\em Discrete Mathematics} 341, 2018), concerning permutations with the same pinnacle set. Given $π\in S_n$, a {\em pinnacle} of $π$ is an element $π_i$ ($i\neq 1,n$) such that $π_{i-1}<π_i>π_{i+1}$. The question is: given $π,π'\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $π$ into $π'$ such that all the intermediate permutations have pinnacle set $S$? We introduce {\em balanced reversals}, defined as reversals that do not modify the pinnacle set of the permutation to which they are applied. Then we show that $π$ may be sorted by balanced reversals (i.e. transformed into a standard permutation $\Id_S$), implying that $π$ may be transformed into $π'$ using at most $4n-2\min\{p,3\}$ balanced reversals, where $p=|S|\geq 1$. In case $p=0$, at most $2n-1$ balanced reversals are needed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Decomposing Cubic Graphs into Connected Subgraphs of Size Three

Let $S=\{K_{1,3},K_3,P_4\}$ be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph $G$ into graphs taken from any non-empty $S'\subseteq S$. The problem is known to be NP-complete for any possible choice of $S'$ in general graphs. In this paper, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of $S'$. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterisations of $S'$-decomposable cubic graphs in some cases.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Log-Lists and Their Applications to Sorting by Transpositions, Reversals and Block-Interchanges

Link-cut trees have been introduced by D.D. Sleator and R.E. Tarjan (Journal of Computer and System Sciences, 1983) with the aim of efficiently maintaining a forest of vertex-disjoint dynamic rooted trees under cut and link operations. These operations respectively disconnect a subtree from a tree, and join two trees by an edge. Additionally, link-cut trees allow to change the root of a tree and to perform a number of updates and queries on cost values defined on the arcs of the trees. All these operations are performed in $O(\log\, n)$ amortized or worst-case time, depending on the implementation, where $n$ is the total size of the forest. In this paper, we show that a list of elements implemented using link-cut trees (we call it a $\log$-list) allows us to obtain a common running time of $O(\log\, n)$ for the classical operations on lists, but also for some other essential operations that usually take linear time on lists. Such operations require to find the minimum/maximum element in a sublist defined by its endpoints, the position of a given element in the list or the element placed at a given position in the list; or they require to add a value $a$, or to multiply by $-1$, all the elements in a sublist. Furthermore, we use $\log$-lists to implement several existing algorithms for sorting permutations by transpositions and/or reversals and/or block-interchanges, and obtain $O(n\,\log\, n)$ running time for all of them. In this way, the running time of several algorithms is improved, whereas in other cases our algorithms perform as well as the best existing implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

NP-hardness of sortedness constraints

In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, several sortedness constraints have been defined, for which propagation algorithms are available, but for which the tractability is not settled. We show that the sort(U,V) constraint (Older et. al, 1995) is intractable for integer variables whose domains are not limited to intervals. As a consequence, the similar result holds for the sort(U,V, P) constraint (Zhou, 1996). Moreover, the intractability holds even under the stability condition present in the recently introduced keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014), and requiring that the order of the variables with the same value in the list U be preserved in the list V. Therefore, keysorting(U,V,Keys,P) is intractable as well.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Permutation Reconstruction from MinMax-Betweenness Constraints

In this paper, we investigate the reconstruction of permutations on {1, 2, ..., n} from betweenness constraints involving the minimum and the maximum element located between t and t+1, for all t=1, 2, ..., n-1. We propose two variants of the problem (directed and undirected), and focus first on the directed version, for which we draw up general features and design a polynomial algorithm in a particular case. Then, we investigate necessary and sufficient conditions for the uniqueness of the reconstruction in both directed and undirected versions, using a parameter k whose variation controls the stringency of the betweenness constraints. We finally point out open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications

Motivated by the study of genome rearrangements, the NP-hard Minimum Common String Partition problems asks, given two strings, to split both strings into an identical set of blocks. We consider an extension of this problem to unbalanced strings, so that some elements may not be covered by any block. We present an efficient fixed-parameter algorithm for the parameters number k of blocks and maximum occurrence d of a letter in either string. We then evaluate this algorithm on bacteria genomes and synthetic data.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Easy identification of generalized common and conserved nested intervals

In this paper we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or a common (resp. conserved) interval that contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the classical notion of nested interval. We exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. We also explain how to count all b-nested intervals in O(Kn) time. New properties of the family of conserved intervals are proposed to do so.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Extending Common Intervals Searching from Permutations to Sequences

Common intervals have been defined as a modelisation of gene clusters in genomes represented either as permutations or as sequences. Whereas optimal algorithms for finding common intervals in permutations exist even for an arbitrary number of permutations, in sequences no optimal algorithm has been proposed yet even for only two sequences. Surprisingly enough, when sequences are reduced to permutations, the existing algorithms perform far from the optimum, showing that their performances are not dependent, as they should be, on the structural complexity of the input sequences. In this paper, we propose to characterize the structure of a sequence by the number $q$ of different dominating orders composing it (called the domination number), and to use a recent algorithm for permutations in order to devise a new algorithm for two sequences. Its running time is in $O(q_1q_2p+q_1n_1+q_2n_2+N)$, where $n_1, n_2$ are the sizes of the two sequences, $q_1,q_2$ are their respective domination numbers, $p$ is the alphabet size and $N$ is the number of solutions to output. This algorithm performs better as $q_1$ and/or $q_2$ reduce, and when the two sequences are reduced to permutations (i.e. when $q_1=q_2=1$) it has the same running time as the best algorithms for permutations. It is also the first algorithm for sequences whose running time involves the parameter size of the solution. As a counterpart, when $q_1$ and $q_2$ are of $O(n_1)$ and $O(n_2)$ respectively, the algorithm is less efficient than other approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

MinMax-Profiles: A Unifying View of Common Intervals, Nested Common Intervals and Conserved Intervals of K Permutations

Common intervals of K permutations over the same set of n elements were firstly investigated by T. Uno and M.Yagiura (Algorithmica, 26:290:309, 2000), who proposed an efficient algorithm to find common intervals when K=2. Several particular classes of intervals have been defined since then, e.g. conserved intervals and nested common intervals, with applications mainly in genome comparison. Each such class, including common intervals, led to the development of a specific algorithmic approach for K=2, and - except for nested common intervals - for its extension to an arbitrary K. In this paper, we propose a common and efficient algorithmic framework for finding different types of common intervals in a set P of K permutations, with arbitrary K. Our generic algorithm is based on a global representation of the information stored in P, called the MinMax-profile of P, and an efficient data structure, called an LR-stack, that we introduce here. We show that common intervals (and their subclasses of irreducible common intervals and same-sign common intervals), nested common intervals (and their subclass of maximal nested common intervals) as well as conserved intervals (and their subclass of irreducible conserved intervals) may be obtained by appropriately setting the parameters of our algorithm in each case. All the resulting algorithms run in O(Kn+N)-time and need O(n) additional space, where N is the number of solutions. The algorithms for nested common intervals and maximal nested common intervals are new for K>2, in the sense that no other algorithm has been given so far to solve the problem with the same complexity, or better. The other algorithms are as efficient as the best known algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Pancake Flipping is Hard

Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP-hard, thus answering the long-standing question of its computational complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sorting by Transpositions is Difficult

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the Sorting by Transpositions problem, has been introduced by Bafna and Pevzner in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is NP-hard. As a corollary of our result, we also prove that the following problem is NP-hard: given a permutation pi, is it possible to sort pi using db(pi)/3 permutations, where db(pi) is the number of breakpoints of pi?

0 citations0 reviewsNo code linkedOpen access