The Study of Multiple Ordering Management in C1P (Consecutive-Ones Property)

INTRODUCTION

A binary matrix M has the Consecutive-Ones Property (C1P) if there exists a stage of its columns with the end goal that all 1's in each row are consecutive. Choosing if a matrix has the C1P should be possible in direct reality. This issue has been considered in genomics, for issues, for example, physical mapping or genealogical genome reproduction. As of late, Wittler and Stoye in, persuaded by taking care of copied genes in recreating tribal gene groups, presented a generalized issue: Given a few arrangements of genes and a most extreme variety for every gene, choose whether there exists a sequence of genes which meets the assortment limitation for every gene and in which each arrangement of genes happens consecutively. This can be stated as far as a binary matrix, where a column relates to a gene and a lot of genes is spoken to by a row containing a 1 for every gene in the set in the separate column and 0's in every other column. Presently every column c of the matrix is given an assortment limit m(c): M fulfills the mC1P (for C1P with variety) if there is a sequence S of columns of M, in which at most m(c) events of column c can show up, and for each row r of M, the columns containing 1 in r show up consecutively some place in S. The sequence S compares then to a substantial gene arrange. Choosing if a binary matrix M with assortment fulfills the mC1P is tractable if each row of M contains at most two passages 1 (which relates in gene bunches models to gene adjacencies), however the issue is NP-finished if M contains rows with at most three sections 1. The mC1P can likewise be identified with gene closeness investigation with copied genes. In this work, we present a tractability result for a limited mC1P choice issue. After some specialized starters (Section 2), we give in Section 3 a tractability result for a group of matrices where each row of M has at most one passage 1 in columns with assortment more prominent than one, or precisely two passages in columns with variety more noteworthy than one and no different sections. This outcome is persuaded by dealing with telomeres in hereditary gene arrange reproduction (depicted in Appendix A). Our evidences depend on two established ideas: PQ-trees and Eulerian cycles in charts. We close by talking about future work.

Give M a chance to be a binary matrix, with m rows R = {r1,...,rm}, n columns C = {c1,..., cn} and I passages 1. We speak to a row r of M as a subset of C, characterized as the arrangement of c with the end goal that M[r, q] = 1. A variety vector m for M is a sequence of positive integers [m(ci),..., m(cn)]: m(cf) is known as the assortment of column cp A column c with variety m(c) > 1 is known as a multicolumn and a row r containing a multicolumn (i.e., M[r, c] = 1 for some column c with m(c) > 1) is known as a multirow. A multirow that does not that contains something like two passages 1 in non-multicolumns, there exists a row r which is a duplicate of r where all sections in multicolumns have been disposed of (i.e., changed from 1 to 0). We mean by M the binary matrix got from M by disposing of all multicolumns. In this work, we expect that all matrices we manage have coordinated multirows except if generally expressed. Figure 1 shows the above definitions Fig. 1. Left: Binary matrix M, with coordinated multirows. Let m( 1) = • = m(5) = 1 and m(a) = m(b) = 2: an and b are multicolumns and ri, r3 and r4 are multirows. Row r3 isn't negligible, on the grounds that it contains r4. Right: The relating matrix M. Since in M, by definition A = fi for all multirowsri, the coordinated multirows are disposed of. Definition 1. Matrix M has the Consecutive-Ones Property with assortment (mC1P) for variety vector m if there exists a sequence S = si . .. sp on the letter set C with the end goal that it meets (1) theconsecutivity necessity: for each row r of M there are two integers j,k, with j < k to such an extent that r = {sj, Sj+i, .. ., Sk} (the columns in r are consecutive in S), and (2) the assortment prerequisite: every c shows up at most m(q) times. The sequence S is then called a mClP-ordering of M. Given row {1, 2, 3,4}, a case of a sequence that fulfills condition (1) of the above definition is the sequence 5142435, since {1, 2, 3, 4} = {1, 4, 2,4, 3}. The mC1P generalizes the traditional Consecutive-Ones Property (C1P), where m(cf) = 1 for each q. Lemma 1 beneath, whose verification is direct, relates the two issues. Lemma 1. Each mC1P-ordering of M with variety vector m contains a C1P-ordering of M as a subsequence. As a consequence, on the off chance that a binary matrix M has the mC1P, M has the C1P. broaden a C1P-ordering of M into a mC1P-ordering of M by including duplicates of multicolumns. Note that the matrix M in Figure 1 does not have C1P, and thus, M does not have mC1P. Nonetheless, in the event that we preclude column r5, 12345 is a C1P ordering of M, which can be reached out to the accompanying mC1P-ordering of M: a6123456. To represent the way that there can be an exponential number of C1P-orderings of M, we use PQ-trees, a direct size structure that can depict all C1P-orderings of M, characterized underneath. For an increasingly total treatment of PQ-trees, we allude the peruser to. Definition 2. A PQ-tree on C is a rooted ordered tree with leaves marked by C and two sorts of interior nodes, P-nodes and Q-nodes. Every P-node has something like two youngsters and every Q-node has somewhere around three children. The boondocks F(T) of a PQ-tree T is the sequence of C acquired by perusing the marks of its leaves from left to right. The wilderness of a node N in T is the outskirts of the subtree rooted at N. Let {F(N)} be the arrangement of components showing up in the sequence F(N). Two PQ-trees are proportional on the off chance that one can be acquired from the other by applying a sequence of the accompanying change rules: (RP) discretionarily permute the offspring of a P-node; (RQ) switch the order of the offspring of a Q-node. Theorem 1. If a binary matrix M has the C1P, there exists an exceptional comparability class PQM of PQ-trees with the property that there is a coordinated correspondence between the C1P-orderings of M and the wildernesses of the PQ-trees of PQM, and a PQ-tree having a place with PQM can be built in straight time. Each PQ-tree in the identicalness class PQM fulfills the accompanying properties (that are certainly given in [3, 9]) which we will use in this paper. Property 1. Give M a chance to be a binary matrix that has C1P with rows R and T a PQ-tree in the identicalness class PQM . At that point 1. for each row r G R, there is a node N in T with the end goal that either {F(N)} = r, if N is a P-node, or r is consecutive in F(N), if N is a Q-node; 2. for each node N unique in relation to the root of T, there is a row r G R with the end goal that {F(N)} C r; and

{F(N1)}U{F(N2)} C r. At long last, we review quickly the system used to demonstrate that matrices with two passages 1 for each row (more often than not called matrices of degree 2) shape a class of tractable cases for choosing the mC1P as we will utilize it to demonstrate our principle result. Such matrices can be normally spoken to as a gathering of adjacency requirements A = {{a*, 6j}}m=1 on the set C, where a* = b* and the accumulation is a set (no copy components). Accumulation An is reliable as for m if there is a sequence S on C with the end goal that every adjacency is consecutive in S. We will allude to this sequence as a consistency sequence of An and m. Note that a mC1P-ordering of M is a consistency sequence of the comparing accumulation An and m, and the other way around, and thus, M has the mC1P for m if and just if An is predictable regarding m. Given a gathering of adjacencies A, we characterize the graph Ga with vertex set C and edges given by adjacencies. Theorem 2. An accumulation of adjacencies An is steady concerning an assortment vector m if and if for all c* G C, degreeG (c*) < 2m(cj) and for each associated segment B C of GA, for no less than one c G B, degreeG (cj) < 2m(cj). The above theorem depends on the way that the graph GA fulfilling the above conditions can be reached out to a multigraph on C U {c0} that has an Eulerian cycle. It very well may be effectively observed that the verification exhibited in [12] applies to generalized adjacencies, where we permit a* = b* and the accumulation to be a multiset, and we necessitate that every adjacency in A shows up in S in a novel position. Note that GA is currently a multigraph with self-circles. We have the accompanying culmination. Culmination 1. A gathering of generalized adjacencies An is reliable as for a variety vector m if and if for all cj G C, degreeG (cj) < 2m(cj) and for each associated segment B CC of G A, for no less than one cj G B, degree^(cj) < 2m(cj).

Our principle result is that choosing the mC1P is tractable for a substantial group of matrices with limitations on the most extreme number of passages 1 in multicolumns a row can have. The inspiration for concentrate this specific group of matrices emerges from fusing data on telomeres in familial gene order recreation (Appendix A). contains it is possible that (I) at most one passage 1 in multicolumns, or (ii) two sections 1 in multicolumns and no different sections. Choosing if M has the mC1P for m should be possible in polynomial reality We split the evidence into two sections. In Section 3.1, we think about the case (2i) where M with variety vector m contains a solitary multicolumn, and we demonstrate that choosing if M has the mC1P for m should be possible proficiently utilizing PQ-trees. At that point, in Section 3.2, we demonstrate to deal with the general case utilizing Corollary 1 which depends on Eulerian cycles. At long last, in Section 3.3, we give a calculation for building a PQ-tree which portrays all sequences that fulfill the consecutivity necessity (condition (1) of Definition 1).

We expect that the variety vector m characterizes just a single multicolumn signified by C. As per Lemma 1, M fulfills the mC1P just if M has the C1P, which can be checked in direct time (Theorem 1). Accept that M has the C1P and given T a chance to be a PQ-tree from the identicalness class PQM . We at that point go for finding a PQ-tree from PQM (by applying activities (RP) and (RQ) on T) whose boondocks can be reached out to a legitimate mC1P-ordering by embeddings duplicates of C. We state that embeddings a duplicate of C into F(T) breaks a row r of M if r isn't consecutive in the subsequent sequence. A model is given in Figure 2 Fig. 2. Left: Binary matrix M, with coordinated multirows. Let m(c') = 2. Right: PQ-tree having a place with the equality class PQmm . P-nodes are spoken to by roundabout nodes and Q-nodes by rectangular nodes. A case of a legitimate mC1P-ordering is cC 1234 C 78956 which is gotten by taking the identical PQ-tree with boondocks 123478956 and embeddings two duplicates of cC into the relating positions. Notice that embeddingscC somewhere in the range of 2 and 3 would break row r2. Representation of Algorithm 1.LCA(ri) and the individual fragments of LCA(r3,4) are featured in dark and the particular ways are portrayed by Review that rows are subsets of C. As M has coordinated multirows, all rows in M are additionally rows in M. Since the consecutivity of the 1's in each row of M in the outskirts F(T) must be kept up while embeddings duplicates of C, no C can be embedded into a position where it breaks any row of M. Lemma 2 beneath is a consequence of this perception. Lemma 2. Give M a chance to be a binary matrix with coordinated multirows, and m be an assortment vector characterizing precisely one multicolumn cC. Expect that M has the mC1P, and let T be a PQ-tree from PQM and T' an augmentation of T whose wilderness F(T1) is a mC1P-ordering of M. 1. If the root of T is a P-node, at that point, for every tyke node N of the root,C can only appear as the first or last component of the wilderness F (N) in T'. 2. If the root of T is a Q-node, the duplicates of C in T' can just show up as the first as well as last component of the wilderness F(T'). Proof:. It pursues by Property 1.2 that for each youngster N of the root of T, any match of consecutive leaves in F(N) has a place with a row of M, and henceforth, embeddings C between these leaves breaks this row. What's more, on the off chance that the root of T is a Q-node, by Property 1.3, for any two consecutive youngsters N1 and N2 of the root, there is a row of M that contains components of F(N1) and of F(N2). This keeps the addition of c' into root somewhere in the range of N1 and N2 as this would break such a row. Thus c' can seem just at the furthest points of F(T'). Lemma 2 discounts numerous situations in F(T) where to embed duplicates of c': in fact, duplicates of d must be embedded at furthest points of the subsequences of F(T) shaped by offspring of the root (and just at the limits of F(T), if the root is a Q-node). Then again, each multirow determines a position where a duplicate of c' must be embedded. These two limitations offer ascent to a polynomial calculation which we portray in the accompanying. Algorithm 1 begins with a PQ-tree for M and works in two phases. First (Step 3), in light of Lemma 2, it checks if there is an approach to permute nodes in the subtrees rooted at every offspring of the root with the end goal that for each multirow r = r U {c'}, rows in r show up as a prefix or an addition of the outskirts of some tyke. To fulfill the consecutivity necessity for each multirow r it is sufficient to include duplicates of c' to F (T) previously or after the boondocks of the offspring of the root containing r. To fulfill the fundamental thought is that we can spare one duplicate of c' if a youngster requiring a duplicate of c' on the privilege is trailed by a tyke requiring a duplicate of c' on the left. Regardless of whether enough duplicates of c' can be spared to fulfill the assortment necessity is checked in Steps 4-5. Let r = r U {c'} be a multirow. By Property 1.1, there is in T either a P-node that contains precisely the columns in f in its subtree, or a Q-node with a section of at least two consecutive youngsters which together contain precisely the columns in r in their subtrees. This node is the minimum basic precursor in T of the columns in r, and henceforth, will be indicated by LCA(r) Presently to contend that Algorithm 1 is right. On the off chance that condition 3.c.i applies, r would require the inclusion of a duplicate of c' inside F(U) in any PQ-tree of PQM, which repudiates Lemma 2. The ways demonstrate positions where duplicates of c' must be added to the boondocks so the consecutivity necessity is fulfilled. Following Lemma 2, we need to check whether we can change T with the end goal that all ways lie outwardly of the subtree of an offspring of the root of T. In the event that conditions 3.c.ii-3.c.iv apply, there are at least two contending multirows, and we can't change T with the end goal that the majority of the relating ways lie outwardly of the subtree of an offspring of the root of T. Ways that are sub-ways of each other are rejected by not considering any multirow r = r U {c'} which contains another multirow r' = r' U {c'} (line 3). These rows don't should be considered at this stage, in light of the fact that in any ordering with c' contiguous the components in r', since f' C f, c' is likewise nearby the components in r. On the off chance that the root of T is a P-node, we need to consider the offspring of the root node independently: We could embed a duplicate of c' on the two sides of an outskirts of an offspring of the root, i.e., at most two ways can join better than a tyke node. In levels underneath the root, just a single way can be moved to the border of the subtree, i.e., no two edges can join.

(RQ)) in the nodes on the way Pr (barring the root) so the wilderness of N = LCA(r) shows up as a prefix or postfix of the boondocks of N', where N' is an offspring of the root lying on the way Pr. Next, we will demonstrate that every one of these changes can be performed at the same time with no contention. Clearly, the contentions could possibly happen if the ways Pr share vertices other than root. Condition 3.c.iv ensures that there are never at least three negligible multirows in the equivalent subtree rooted at a youngster N' of the root. Condition 3.c.iii ensures that if there are two negligible multirows in the equivalent subtree rooted at a youngster N' of the root, their ways must meet just in N', and thus, one can show up as a prefix and one as a postfix of the outskirts of N'. In any case, if the root is a Q-node, by Lemma 2, column c' can be appended just on one side of the boondocks of N', and subsequently, just a single insignificant multirow can show up in the subtree rooted at N', which is checked in condition 3.c.ii. Subsequently, if Step 3 prevails for all rows, there is a PQ-tree in PQM from which we can get a sequence of the columns satisfying the consecutivity necessity of M by embeddings duplicates of c' into its boondocks at positions demonstrated by the ways of multirows. Stages 4-5 check if the variety limitation forced by m can be fulfilled. Note, that on the off chance that the root of T is a Q-node (Step 4), the variety limitation is fulfilled since m(c') > 2. In Step 5, we check the quantity of duplicates of c' required to fulfill all multirows. The position where to embed these duplicates are given by the ways. Since the root of T is a P-node, we can revamp the offspring of the root to such an extent that one duplicate of c' would agree with two ways (from neighboring youngsters). For example, we can avariciously combine nodes with one way each, utilizing [K1/2] duplicates and afterward incorporate nodes with two ways (one way on each side) in the middle of, requiring one further duplicate every, K2 altogether. On the off chance that K1 =0 and K2 > 0, tying the two-way nodes results in K2 + 1 duplicates of c'. It is anything but difficult to see that this joining procedure is ideal. On the off chance that the quantity of required duplicates of c' does not surpass the given greatest variety m(c'), the given matrix M with assortment vector m has the mC1P. At long last, to finish the evidence of the rightness of the calculation, we just need to see that the consequence of Algorithm 1 does not rely upon the decision of the PQ-tree T of PQM, as the LCAs and ways are invariant under the change rules (RQ) and (RP). The investigation of the reality multifaceted nature of Algorithm 1 is as per the following. To begin with, in O(n) space. Next, Step 3 is made out of at most m cycles, every one of them requiring time O(n), the greatest length of a way from N to the root of T, as every way is clearly prepared in time straight in its length. This gives an O(mn) time multifaceted nature for Step 3. For comparative reasons, Step 4 can be accomplished in time O(mn), which gives a general most pessimistic scenario time unpredictability of O(mn). This finishes the evidence of the instance of a solitary multicolumn in Theorem 3

Proof (Proof of Theorem 3). Given matrix M with assortment vector m and having coordinated multirows, let C' be its arrangement of multicolumns. A multirow containing multicolumn c' G C', will be known as a c'- multirow. Calculation 2 works in indistinguishable two phases from Algorithm 1. Be that as it may, the second stage is progressively perplexing. It requires building the accumulation of generalized adjacencies An on set C' U {c0} by supplanting every offspring of the root of the PQ-tree T for M by an adjacency and after that applying Corollary 1. Accuracy of Step 1 pursues from the rightness of the main phase of Algorithm 1. In the event that Step 1 succeeds, we can expect that the root of T is a P-node (the situation when the root is a Q-node is taken care of in Step 1), and henceforth, it is sufficient to fulfill the assortment necessity by permuting the offspring of the root and conceivably turning around the order of the boondocks of a few youngsters. Give n a chance to be this order of offspring of the root. In Step 2, the calculation develops the multiset of generalized adjacencies A whose consistency sequence (delivered in Step 3) portrays the best approach to do this as pursues. Youngsters that have a place with zero ways characterized by multirows won't present any adjacency imperatives and can be set toward the finish of n in any order and introduction. For some other offspring of the root, we have an exceptional position in the consistency sequence, henceforth we can order and arrange these kids dependent on these positions. Next, we embed duplicates of multicolumns as pursues. For every subsequence c1c2c3 of the consistency sequence, where adjacency {c1,c2} compares to kid N1 and {c2,c3} to N2, if c2 = c0, we embed a duplicate of c2 between the boondocks of N1 and N2 in F(T). Henceforth, the quantity of duplicates of a multicolumn c' G C' is equivalent to the quantity of its events in the consistency sequence. In this way, the boondocks F(T) with every single required duplicate of multicolumns embedded fulfills the variety necessity given by m. It is anything but difficult to see that on the off chance that there is a mC1P ordering of M, we can remove from it an The investigation of the time multifaceted nature is as per the following. The primary phase of the calculation is a subroutine of Algorithm 1, and thus, has a reality unpredictability of order O(mn). Since the quantity of offspring of the root of T that have a place with no less than one way characterized by multirows is at most m, the quantity of adjacencies in An is at most m, and thus, constructing A requires some investment O(m). At long last, checking the degree conditions (applying Corollary 1) requires some investment O(n). Henceforth, the aggregate reality unpredictability of the calculation is O(mn). At long last, Algorithm 2 can likewise be effectively stretched out to the situation when the matrix additionally contains rows of degree 2 containing two multicolumns, as pursues. To start with, we run Steps 1 and 2 where we overlook multirows containing two multicolumns. At that point, we add to A likewise an adjacency for each such multirow. At long last, we run Step 3 of the calculation on this new accumulation A. It is anything but difficult to see that the timemultifaceted nature of this new calculation is still O(mn). Consequently, the theorem holds.

Here, we depict how a given PQ-tree T G PQM can be increased to a PQ-tree T' which speaks to the arrangement of all sequences S, up to "siphoning" events of multicolumns, that fulfill the consecutivity prerequisite (condition (1) of Definition 1) in that the wilderness of any tree in the equality class of T' is such a sequence S. In any case, not all wildernesses meet the assortment necessity (condition (2) of Definition 1). For a few trees in the proportionality class of T', the individual boondocks contains sets of nearby events of a multicolumn c', every one of which can be supplanted by one event of c' without breaking any row of M (disregarding the consecutivity necessity). This lessens the quantity of utilized duplicates of the multicolumns. Just such abbreviated boondocks which meet the variety prerequisite are legitimate mC1P orderings, and, truth be told, the arrangement of such shortented wildernesses is actually the arrangement of substantial mC1P orderings of M. Figure 3 demonstrates a model. To develop an increased PQ-tree T', we process the first tree T in a base up mold along the ways Pr characterized in Algorithm 1, beginning with the LCAs. We supplant a LCA by another Q-node which has a duplicate of its comparing multicolum c' as its first kid and further youngsters, contingent upon whether the LCA itself and its parent are P or Q-nodes. These instinctive change rules are definite in Figure 4. Fig. 3. Enlarged PQ-tree T' for the matrix given in Figure 2. (Indeed, to get an expanded PQ-tree from the first PQ-tree appeared in Figure 2, no adjustments are vital other than connecting leaf nodes named c' at suitable areas.) Only the trees in the identicalness class of T' where the left half of the correct Q-node is put nearby the left Q-node have abbreviated boondocks that meet the variety necessity (m(c') = 2), for instance, c' 12 3 4 c' 7 8 9 5 6. Fig. 4. Change rules for the LCAs to build an expanded PQ-tree. A LCA and its parent node are supplanted by the nodes appeared on the right. The LCA (or the fragment of a LCA, separately) are featured in dim. Fig. 5. Change rules for base up cycle to develop an expanded PQ-tree. A recently made Q-node and its parent node are supplanted by the nodes appeared on the right.

Fig. 6. Uncommon change rules for base up emphasis to build an enlarged PQ-tree. A recently made Q-node two dimensions underneath the root node and its parent node are supplanted by the nodes appeared on the right. This procedure is iterated until the point when we come to the root node. Since a node that is a child of the root can be contained in two ways, discrete (yet comparable) rules are required, outlined in Figure 6. Further explicit tenets which apply if a LCA is an offspring of the root of T or if the root node is a Q-node are clear. Now and again, in the wake of generating the tree as depicted above, disentanglements can be completed, for example, supplanting a P-node with a solitary kid by an immediate edge or substituting a Q-node with two youngsters by a P node. Comparably to Algorithm 1, that just checks if a matrix has the mC1P, the above construction of an expandedPQ-tree T' can be done in O(mn) time.

In the present work, we broaden the area of tractable examples of choosing the C1P with variety for binary matrices. Our methodology depends on recently utilized systems to choose the C1P and easier occasions of the mC1P, and answers a characteristic issue in recreating hereditary gene orders. A few inquiries stay open. Normally, one can request to loosen up the condition that M has coordinated multirows, which is urgent in our evidences. It appears to be anyway that the issue turns out to be hard for this situation, and some less unbending limitations on M would then must be acquainted with recoup tractability. Additionally it is available to show an expansion of the idea of the PQ-tree that could encode all mC1P-orderings of a binary matrix that fulfills this property. Notwithstanding for the instance of a matrix with coordinated multirows, our systems lead to an information structure which just catches the consecutively necessity however not the variety prerequisite. From an algorithmic multifaceted nature perspective, our calculation has an O(mn) time unpredictability, and it stays open to check whether this case can be tackled in O(m + n + £) time.

D. G. Kendall (1969). Incidence matrices, interval graphs and seriation in archaeology.Pacific J. Math., 28, pp. 565-570. D. R. Fulkerson and O. A. Gross (2002). Incidence matrices and interval graphs.Pacific J. Math., 15, pp. 835-855.

S. P. Ghosh (2002). File organization: the consecutive retrieval property. Commun. ACM, 15, pp. 802-808. Zaky Adam, Monique Turmel, Claude Lemieux, and David Sanko_ (2006). Common intervals and symmetric di_erence in a model-free phylogenomics, with an application to streptophyte evolution.In Comparative Genomics'06, pages 63-74. Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, and Geo_rey Zweig (1994). Physical mapping of chromosomes using unique probes. In Proceedings of the _fth annual ACM- SIAM symposium on Discrete algorithms, SODA'94, pages 489{500, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics. Seymour Benzer (1959). On the topology of the genetic _new structure. Proc. Nat. Acad. Sci. USA, 45: pp. 1607-1620. Anne Bergeron, Mathieu Blanchette, Annie Chateau, and Cedric Chauve (2004). Reconstructing ancestral gene orders using conserved intervals. In Proc. Fourth Intl Workshop Algorithms in Bioinformatics WABI04, pages 14-25. Springer, 2004. Guillaume Blin, Romeo Rizzi, and St_ephaneVialette (2010). A faster algorithm for finding minimum tucker submatrices. In Proceedings of the Programs, proofs, process and 6th international conference on Computability in Europe, CiE'10, pages 69-77, Berlin, Heidelberg, 2010. Springer-Verlag. G. C˘alinescu, A. Dumitrescu, H. J. Karloff, and P.J. Wan (2005). Separating points by M. Dom and S. Sikdar (2008). The parameterized complexity of the rectangle stabbing problem and its variants. In Proc. 2nd FAW, volume 5059 of LNCS, pages 288–299. Springer, 2008. R. G. Downey and M. R. Fellows (1999). Parameterized Complexity. Springer, 1999. G. Even, R. Levi, D. Rawitz, B. Schieber, S. Shahar, and M. Sviridenko (2008). Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Trans. Algorithms, 4(3), Article 34, 2008. M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette (2008). On the parameterized complexity of multiple-interval graph problems. Manuscript, 2008. J. Flum and M. Grohe (2006). Parameterized Complexity Theory. Springer, 2006.

Senior Lecturer vijay7092@gmail.com