Zobrazeno 1 - 10
of 96
pro vyhledávání: '"Pranabendu Misra"'
Publikováno v:
ACM Transactions on Algorithms. 19:1-68
Given a graph G and an integer k , the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S ⊆ V ( G ) of size at most k such that G-S is an interval graph. This problem is known to be NP -complete (according to Yannakakis at
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7530427a0802378b07d3a1ecd0d538fd
https://doi.org/10.1145/3571075
https://doi.org/10.1145/3571075
Publikováno v:
Journal of Graph Theory. 102:702-727
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::57178fcd4492e1c5265acc9597e46453
https://doi.org/10.1002/jgt.22895
https://doi.org/10.1002/jgt.22895
Publikováno v:
Algorithmica. 84:2622-2641
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2febf31cafcadd7a41df786b3c22b381
https://doi.org/10.1007/s00453-022-00959-3
https://doi.org/10.1007/s00453-022-00959-3
Autor:
Saket Saurabh, Pranabendu Misra, Joydeep Mukherjee, Geevarghese Philip, Daniel Lokshtanov, Fahad Panolan
Publikováno v:
ACM Transactions on Algorithms. 17:1-14
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2d09687e1443a359296656bd3a8fedc1
https://doi.org/10.1145/3446969
https://doi.org/10.1145/3446969
Publikováno v:
Theoretical Computer Science. 954:113803
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bc21389e44dc13020d130a1fb02ea6ef
https://doi.org/10.1016/j.tcs.2023.113803
https://doi.org/10.1016/j.tcs.2023.113803
Publikováno v:
ACM Transactions on Algorithms. 16:1-38
For a family of graphs ℱ, the Weighted ℱ Vertex Deletion problem, is defined as follows: given an n -vertex undirected graph G and a weight function w : V ( G ) ℝ, find a minimum weight subset S ⊆ V ( G ) such that G - S belongs to ℱ. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d8570fa4043af8d60a1aaa578faef6da
https://doi.org/10.1145/3389338
https://doi.org/10.1145/3389338
Publikováno v:
Theoretical Computer Science. 818:51-59
Given a bipartite graph \(G=(U\uplus V,E)\), a linear representation of the transversal matroid associated with G on the ground set U, can be constructed in randomized polynomial time. In fact one can get a linear representation deterministically in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d148687ed10d1b434a0c96186148290a
https://doi.org/10.1016/j.tcs.2018.02.029
https://doi.org/10.1016/j.tcs.2018.02.029
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:
Theory of Computing Systems. 64:1067-1093
Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S is in π. In this paper, we introdu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::458b51654dab1af1c946daef2fa8c29f
https://doi.org/10.1007/s00224-019-09964-6
https://doi.org/10.1007/s00224-019-09964-6
Publikováno v:
EC
We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocati
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1a903fc23b1d6a48fac93fce18fa14eb
http://arxiv.org/abs/2103.01628
http://arxiv.org/abs/2103.01628
