Search

Your search keyword '"Maňuch, Ján"' showing total 207 results
Start Over Author "Maňuch, Ján"
207 results on '"Maňuch, Ján"'

1. Weak Coverage of a Rectangular Barrier

Author

Dobrev, Stefan, Kranakis, Evangelos, Krizanc, Danny, Lafond, Manuel, Manuch, Jan, Narayanan, Lata, Opatrny, Jaroslav, and Stacho, Ladislav

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Mathematics - Optimization and Control
Abstract

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by the sensors (MinMax). We give an O(n^{3/2}) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions, while it is NP-hard for heterogeneous sensor ranges. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.

Published
2017

2. Combinatorial RNA Design Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models

Author

Haleš, Jozef, Héliou, Alice, Maňuch, Ján, Ponty, Yann, and Stacho, Ladislav

Subjects
Quantitative Biology - Quantitative Methods, Quantitative Biology - Biomolecules
Abstract

We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the contributions of base pairs are additive and independent: the purely combinatorial Watson-Crick model, which only allows equally-contributing A -- U and C -- G base pairs, and the real-valued Nussinov-Jacobson model, which associates arbitrary energies to A -- U, C -- G and G -- U base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the four-letter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in $\Theta$(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating relaxation of the design, and provide a $\Theta$(n) algorithm which, given a structure S that avoids two trivially non-designable motifs, transforms S into a designable structure constructively by adding at most one base-pair to each of its stems., Comment: To appear

Published
2016

3. Ordering with precedence constraints and budget minimization

Author

Rafiey, Akbar, Kinne, Jeff, Manuch, Ján, and Rafiey, Arash

Subjects
Computer Science - Discrete Mathematics
Abstract

We introduce a variation of the scheduling with precedence constraints problem that has applications to molecular folding and production management. We are given a bipartite graph $H=(B,S)$. Vertices in $B$ are thought of as goods or services that must be \emph{bought} to produce items in $S$ that are to be \emph{sold}. An edge from $j\in S$ to $i\in B$ indicates that the production of $j$ requires the purchase of $i$. Each vertex in $B$ has a cost, and each vertex in $S$ results in some gain. The goal is to obtain an ordering of $B\cup S$ that respects the precedence constraints and maximizes the minimal net profit encountered as the vertices are processed. We call this optimal value the \emph{budget} or \emph{capital} investment required for the bipartite graph, and refer to our problem as \emph{the bipartite graph ordering problem}. The problem is equivalent to a version of an NP-complete molecular folding problem that has been studied recently [12]. Work on the molecular folding problem has focused on heuristic algorithms and exponential-time exact algorithms for the un-weighted problem where costs are $\pm 1$ and when restricted to graphs arising from RNA folding. The bipartite graph present work seeks exact algorithms for solving the bipartite ordering problem. We demonstrate an algorithm that computes the optimal ordering in time $O^*(2^n)$ when $n$ is the number of vertices in the input bipartite graph. Our main result is a general strategy that can be used to find an optimal ordering in polynomial time for bipartite graphs that satisfy certain properties. We apply the technique to a variety of graph classes, obtaining polynomial-time solutions to the bipartite graph ordering problem for bipartite permutation graphs, trivially perfect, co-bipartite graphs, and trees.

Published
2015

4. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm

Author

Haleš, Jozef, Maňuch, Ján, Ponty, Yann, and Stacho, Ladislav

Subjects
Quantitative Biology - Quantitative Methods, Computer Science - Data Structures and Algorithms
Abstract

In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem which aims at finding a sequence that admits a given target as its unique base pair maximizing structure. We provide complete characterizations for the structures that can be designed using restricted alphabets. Under a classic four-letter alphabet, we provide a complete characterization of designable structures without unpaired bases. When unpaired bases are allowed, we provide partial characterizations for classes of designable/undesignable structures, and show that the class of designable structures is closed under the stutter operation. Membership of a given structure to any of the classes can be tested in linear time and, for positive instances, a solution can be found in linear time. Finally, we consider a structure-approximating version of the problem that allows to extend bands (helices) and, assuming that the input structure avoids two motifs, we provide a linear-time algorithm that produces a designable structure with at most twice more base pairs than the input structure., Comment: CPM - 26th Annual Symposium on Combinatorial Pattern Matching, Jun 2015, Ischia Island, Italy. LNCS, 2015

Published
2015

5. Pattern overlap implies runaway growth in hierarchical tile systems

Author

Chen, Ho-Lin, Doty, David, Maňuch, Ján, Rafiey, Arash, and Stacho, Ladislav

Subjects
Computer Science - Computational Geometry
Abstract

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly *and" avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

Published
2014

6. Finding minimum Tucker submatrices

Author

Manuch, Jan and Rafiey, Arash

Subjects
Computer Science - Data Structures and Algorithms
Abstract

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. These matrices are used for DNA physical mapping and ancestral genome reconstruction in computational biology on the other hand they represents a class of convex bipartite graphs and are of interest of algorithm graph theory researchers. Tucker gave a forbidden submartices characterization of matrices that have C1P property in 1972. Booth and Lucker (1976) gave a first linear time recognition algorithm for matrices with C1P property and then in 2002, Habib, et al. gave a simpler linear time recognition algorithm. There has been substantial amount of works on efficiently finding minimum size forbidden submatrix. Our algorithm is at least $n$ times faster than the existing algorithm where $n$ is the number of columns of the input matrix.

Published
2014

9. The complexity of string partitioning

Author

Condon, Anne, Maňuch, Ján, and Thachuk, Chris

Subjects
Computer Science - Computational Complexity, Computer Science - Formal Languages and Automata Theory
Abstract

Given a string $w$ over a finite alphabet $\Sigma$ and an integer $K$, can $w$ be partitioned into strings of length at most $K$, such that there are no \emph{collisions}? We refer to this question as the \emph{string partition} problem and show it is \NP-complete for various definitions of collision and for a number of interesting restrictions including $|\Sigma|=2$. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis., Comment: 14 pages main text + 13 pages appendix. Full version with proofs of an article appearing in the Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Helsinki, Finland, July 2012

Published
2012

10. Hardness Results for the Gapped Consecutive-Ones Property

Author

Chauve, Cedric, Manuch, Jan, and Patterson, Murray

Subjects
Computer Science - Computational Complexity
Abstract

Motivated by problems of comparative genomics and paleogenomics, in [Chauve et al., 2009], the authors introduced the Gapped Consecutive-Ones Property Problem (k,delta)-C1P: given a binary matrix M and two integers k and delta, can the columns of M be permuted such that each row contains at most k blocks of ones and no two consecutive blocks of ones are separated by a gap of more than delta zeros. The classical C1P problem, which is known to be polynomial is equivalent to the (1,0)-C1P problem. They showed that the (2,delta)-C1P Problem is NP-complete for all delta >= 2 and that the (3,1)-C1P problem is NP-complete. They also conjectured that the (k,delta)-C1P Problem is NP-complete for k >= 2, delta >= 1 and (k,delta) =/= (2,1). Here, we prove that this conjecture is true. The only remaining case is the (2,1)-C1P Problem, which could be polynomial-time solvable.

Published
2009

11. Simplifying Analyses of Chemical Reaction Networks for Approximate Majority

Author

Condon, Anne, Hajiaghayi, Monir, Kirkpatrick, David, Maňuch, Ján, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Brijder, Robert, editor, and Qian, Lulu, editor

Published
2017
Full Text
View/download PDF

13. Learning Polytrees with Constant Number of Roots from Data

Author

Safaei, Javad, Maňuch, Ján, Stacho, Ladislav, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Cranefield, Stephen, editor, and Nayak, Abhaya, editor

Published
2013
Full Text
View/download PDF

14. Reachability Bounds for Chemical Reaction Networks and Strand Displacement Systems

Author

Condon, Anne, Kirkpatrick, Bonnie, Maňuch, Ján, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Stefanovic, Darko, editor, and Turberfield, Andrew, editor

Published
2012
Full Text
View/download PDF

15. Turing Universality of Step-Wise and Stage Assembly at Temperature 1

Author

Behsaz, Bahar, Maňuch, Ján, Stacho, Ladislav, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Stefanovic, Darko, editor, and Turberfield, Andrew, editor

Published
2012
Full Text
View/download PDF

16. Less Haste, Less Waste: On Recycling and Its Limits in Strand Displacement Systems

Author

Condon, Anne, Hu, Alan, Maňuch, Ján, Thachuk, Chris, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Cardelli, Luca, editor, and Shih, William, editor

Published
2011
Full Text
View/download PDF

17. Tractability Results for the Consecutive-Ones Property with Multiplicity

Author

Chauve, Cedric, Maňuch, Ján, Patterson, Murray, Wittler, Roland, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Giancarlo, Raffaele, editor, and Manzini, Giovanni, editor

Published
2011
Full Text
View/download PDF

18. Towards a Characterisation of the Generalised Cladistic Character Compatibility Problem for Non-branching Character Trees

Author

Maňuch, Ján, Patterson, Murray, Gupta, Arvind, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Chen, Jianer, editor, Wang, Jianxin, editor, and Zelikovsky, Alexander, editor

Published
2011
Full Text
View/download PDF

19. Complexity of Finding Non-Planar Rectilinear Drawings of Graphs

Author

Maňuch, Ján, Patterson, Murray, Poon, Sheung-Hung, Thachuk, Chris, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Brandes, Ulrik, editor, and Cornelsen, Sabine, editor

Published
2011
Full Text
View/download PDF

20. The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree

Author

Maňuch, Ján, Patterson, Murray, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, and Tannier, Eric, editor

Published
2010
Full Text
View/download PDF

21. Step-Assembly with a Constant Number of Tile Types

Author

Maňuch, Ján, Stacho, Ladislav, Stoll, Christine, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dong, Yingfei, editor, Du, Ding-Zhu, editor, and Ibarra, Oscar, editor

Published
2009
Full Text
View/download PDF

22. NP-Completeness of the Direct Energy Barrier Problem without Pseudoknots

Author

Maňuch, Ján, Thachuk, Chris, Stacho, Ladislav, Condon, Anne, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Deaton, Russell, editor, and Suyama, Akira, editor

Published
2009
Full Text
View/download PDF

23. On the Generalised Character Compatibility Problem for Non-branching Character Trees

Author

Maňuch, Ján, Patterson, Murray, Gupta, Arvind, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Ngo, Hung Q., editor

Published
2009
Full Text
View/download PDF

25. Haplotype Inferring Via Galled-Tree Networks Is NP-Complete

Author

Gupta, Arvind, Maňuch, Ján, Stacho, Ladislav, Zhao, Xiaohong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hu, Xiaodong, editor, and Wang, Jie, editor

Published
2008
Full Text
View/download PDF

26. Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis

Author

Condon, Anne, Maňuch, Ján, Thachuk, Chris, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hu, Xiaodong, editor, and Wang, Jie, editor

Published
2008
Full Text
View/download PDF

28. Constructing Camin-Sokal Phylogenies Via Answer Set Programming

Author

Kavanagh, Jonathan, Mitchell, David, Ternovska, Eugenia, Maňuch, Ján, Zhao, Xiaohong, Gupta, Arvind, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Hermann, Miki, editor, and Voronkov, Andrei, editor

Published
2006
Full Text
View/download PDF

29. Small Phylogeny Problem: Character Evolution Trees

Author

Gupta, Arvind, Maňuch, Ján, Stacho, Ladislav, Zhu, Chenchen, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Sahinalp, Suleyman Cenk, editor, Muthukrishnan, S., editor, and Dogrusoz, Ugur, editor

Published
2004
Full Text
View/download PDF

30. Fault Tolerant Forwarding and Optical Indexes: A Design Theory Approach

Author

Gupta, Arvind, Maňuch, Ján, Stacho, Ladislav, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Královic̆, Ratislav, editor, and Sýkora, Ondrej, editor

Published
2004
Full Text
View/download PDF

35. On defect effect of bi-infinite words

Author

Karhumäki, Juhani, Maňuch, Ján, Plandowski, Wojciech, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Brim, Luboš, editor, Gruska, Jozef, editor, and Zlatuška, Jiří, editor

Published
1998
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results