Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Sudeshna Kolay"'
Publikováno v:
Algorithmica. 84:961-981
The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the vie
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::674f9e4e8d348149c94cdbb340976bcc
https://doi.org/10.1007/s00453-021-00913-9
https://doi.org/10.1007/s00453-021-00913-9
Publikováno v:
Theory of Computing Systems. 66:89-113
The b-Exact Multicover problem takes a universe U of n elements, a family $\mathcal {F}$ of m subsets of U, a function ${\textsf {dem}}: U \rightarrow \{1,\ldots ,b\}$ and a positive integer k, and decides whether there exists a subfamily(set cover)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8579687abc64d4f70266ff4bdb90df8f
https://doi.org/10.1007/s00224-021-10050-z
https://doi.org/10.1007/s00224-021-10050-z
Publikováno v:
Journal of Computer and System Sciences. 109:45-55
In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5f9e11e1cf7430434f743c9dda4269a3
https://doi.org/10.1016/j.jcss.2019.11.001
https://doi.org/10.1016/j.jcss.2019.11.001
Publikováno v:
Theoretical Computer Science. 772:132-142
A harmonious coloring of a graph is a partitioning of its vertex set into parts such that, there are no edges inside each part, and there is at most one edge between any pair of parts. It is known that finding a minimum harmonious coloring number is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7c2b59946a4b3d3e6385f9d152686ba8
https://doi.org/10.1016/j.tcs.2018.12.011
https://doi.org/10.1016/j.tcs.2018.12.011
Publikováno v:
ACM Transactions on Computation Theory. 11:1-28
Given a graph G and a pair ( F 1 , F 2 ) of graph families, the function GDISJ G , F 1 , F 2 takes as input, two induced subgraphs G 1 and G 2 of G , such that G 1 ∈ F 1 and G 2 ∈ F 2 and returns 1 if V ( G 1 )∩ V ( G 2 )=∅ and 0 otherwise. W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6f749c7aec30cf458a82e757cdf5e929
https://doi.org/10.1145/3313234
https://doi.org/10.1145/3313234
We study the Steiner Tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$, a subset $R\subseteq V(G)$ of $t$ vertices and a positive integer $k$, the objective is to decide if there exists a tree $T$ in $G$ that spans over all ver
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6b557e2f2d090d4ef83e618da1ba3a21
http://arxiv.org/abs/2004.09220
http://arxiv.org/abs/2004.09220
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030581497
COCOON
COCOON
The study of parameterized streaming complexity on graph problems was initiated by Fafianie et al. (MFCS’14) and Chitnis et al. (SODA’15 and SODA’16). In this work, we initiate a systematic study of parameterized streaming complexity of graph d
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e4046b3baa5eaa6967cd7cef6ce2b131
https://doi.org/10.1007/978-3-030-58150-3_53
https://doi.org/10.1007/978-3-030-58150-3_53
Publikováno v:
SIAM Journal on Discrete Mathematics, 32(2), 1189-1208. Society for Industrial and Applied Mathematics (SIAM)
Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph H = (U, F), a conflict-free coloring of H refers to a vertex coloring where every hyperedge has a vertex with a unique color
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9d3d35c3bafc2e2e44a7b68ce477e857
https://doi.org/10.1137/16m1107462
https://doi.org/10.1137/16m1107462
Publikováno v:
Theoretical Computer Science. 661:56-64
We study the parameterized complexity of Minimum Volume Packing and Strip Packing . In the two dimensional version the input consists of a set of rectangles S with integer side lengths. In the Minimum Volume Packing problem, given a set of rectangles
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::22db8cffef6201b78614a20062c4ab82
https://doi.org/10.1016/j.tcs.2016.11.034
https://doi.org/10.1016/j.tcs.2016.11.034
Publikováno v:
Algorithmica. 79:667-697
We investigate the parameterized complexity of Generalized Red Blue Set Cover (Gen-RBSC), a generalization of the classic Set Cover problem and the more recently studied Red Blue Set Cover problem. Given a universe U containing b blue elements and r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d1c391186aee405b329a9f39a3ad395b
https://doi.org/10.1007/s00453-016-0216-x
https://doi.org/10.1007/s00453-016-0216-x