8 citations · 31 across the 33 of their papers we have counts for
15 papers · 1 filter
Complexity and Algorithms for Unary Translocation Distance
Maria Constantin, Adrian Miclăuş, Alexandru Popa +1
Given a finite set of integers , a \emph{unary translocation} produces a new set , where and are nonnegative integers satisfying for some…
A novel algorithm for clearing financial obligations between companies -- an application within the Romanian Ministry of Economy
Lucian-Ionut Gavrila, Alexandru Popa
The concept of clearing or netting, as defined in the glossaries of European Central Bank, has a great impact on the economy of a country influencing the exchanges and the interact…
Heuristic algorithms for the Longest Filled Common Subsequence Problem
Radu Stefan Mincu, Alexandru Popa
At CPM 2017, Castelli et al. define and study a new variant of the Longest Common Subsequence Problem, termed the Longest Filled Common Subsequence Problem (LFCS). For the LFCS pro…
A connection between String Covers and Cover Deterministic Finite Tree Automata Minimization
Alexandru Popa, Andrei Tanasescu
Data compression plays a crucial part in the cloud based systems of today. One the fundaments of compression is quasi-periodicity, for which there are several models. We build upon…
Hardness and algorithmic results for the approximate cover problem
Alexandru Popa, Andrei Tanasescu
In CPM 2017, Amir et al. introduce a problem, named \emph{approximate string cover} (\textbf{ACP}), motivated by many aplications including coding and automata theory, formal langu…
An output-sensitive algorithm for the minimization of 2-dimensional String Covers
Alexandru Popa, Andrei Tanasescu
String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis…
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes
Guillaume Ducoffe, Alexandru Popa
We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that…
A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs
Guillaume Ducoffe, Alexandru Popa
We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such a…
Heuristic algorithms for the min-max edge 2-coloring problem
Radu Stefan Mincu, Alexandru Popa
In multi-channel Wireless Mesh Networks (WMN), each node is able to use multiple non-overlapping frequency channels. Raniwala et al. (MC2R 2004, INFOCOM 2005) propose and study sev…
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
David Coudert, Guillaume Ducoffe, Alexandru Popa
Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so…
Parameterized Complexity of Asynchronous Border Minimization
Robert Ganian, Martin Kronegger, Andreas Pfandler +1
Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimi…
Algorithmic and Hardness Results for the Colorful Components Problems
Anna Adamaszek, Alexandru Popa
In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges fr…
The min-max edge q-coloring problem
Tommi Larjomaa, Alexandru Popa
In this paper we introduce and study a new problem named \emph{min-max edge -coloring} which is motivated by applications in wireless mesh networks. The input of the problem con…
Hardness and Approximation of The Asynchronous Border Minimization Problem
Alexandru Popa, Prudence W. H. Wong, Fencol C. C. Yung
We study a combinatorial problem arising from microarrays synthesis. The synthesis is done by a light-directed chemical process. The objective is to minimize unintended illuminatio…
Restricted Common Superstring and Restricted Common Supersequence
Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein +1
The {\em shortest common superstring} and the {\em shortest common supersequence} are two well studied problems having a wide range of applications. In this paper we consider both…