ﻻ يوجد ملخص باللغة العربية
A emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$). There can be three different relations between two disjoint 2-intervals; namely, preceding ($<$), nested ($sqsubset$) and crossing ($between$). Two 2-intervals $D_1$ and $D_2$ are called emph{$R$-comparable} for some $Rin{<,sqsubset,between}$, if either $D_1RD_2$ or $D_2RD_1$. A set $mathcal{D}$ of disjoint 2-intervals is $mathcal{R}$-comparable, for some $mathcal{R}subseteq{<,sqsubset,between}$ and $mathcal{R} eqemptyset$, if every pair of 2-intervals in $mathcal{R}$ are $R$-comparable for some $Rinmathcal{R}$. Given a set of 2-intervals and some $mathcal{R}subseteq{<,sqsubset,between}$, the objective of the emph{2-interval pattern problem} is to find a largest subset of 2-intervals that is $mathcal{R}$-comparable. The 2-interval pattern problem is known to be $W[1]$-hard when $|mathcal{R}|=3$ and $NP$-hard when $|mathcal{R}|=2$ (except for $mathcal{R}={<,sqsubset}$, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing it to be $W[1]$-hard for both $mathcal{R}={sqsubset,between}$ and $mathcal{R}={<,between}$ (when parameterized by the size of an optimal solution); this answers an open question posed by Vialette [Encyclopedia of Algorithms, 2008].
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned i
We show that the problem k-Dominating Set and its several variants including k-Connected Dominating Set, k-Independent Dominating Set, and k-Dominating Clique, when parameterized by the solution size k, are W[1]-hard in either multiple-interval graph
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Barany, Hubard, and Jeronimo [DCG 2008] states that if the sets are convex and emph{wel
A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acy
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximu