Zobrazeno 1 - 10
of 38
pro vyhledávání: '"Amer E. Mouawad"'
Autor:
Anis El Rabaa, Shady Elbassuoni, Jihad Hanna, Amer E. Mouawad, Ayham Olleik, Sihem Amer-Yahia
Publikováno v:
Data Science and Engineering, Vol 8, Iss 2, Pp 146-176 (2023)
Abstract As the number of online labor platforms and the diversity of jobs on these platforms increase, ensuring group fairness for workers needs to be the focus of job-matching services. Risk of discrimination against workers occurs in two different
Externí odkaz:
https://doaj.org/article/7f0e12564d1041d1882132c84b50acb2
Publikováno v:
Algorithms, Vol 11, Iss 2, p 20 (2018)
In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or re
Externí odkaz:
https://doaj.org/article/edd73c0fba554f25bb8e6f36aad66870
Publikováno v:
WALCOM: Algorithms and Computation ISBN: 9783030967307
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ad7a442f6d03c1638d550c4cc2409a2c
https://doi.org/10.1007/978-3-030-96731-4_22
https://doi.org/10.1007/978-3-030-96731-4_22
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5de419310cea0b9f271e68459051b977
https://doi.org/10.1007/978-3-031-15914-5_5
https://doi.org/10.1007/978-3-031-15914-5_5
Publikováno v:
SIAM Journal on Discrete Mathematics
The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention in the fields of graph theo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::36f4ff4f01a238dd142980cd1162c00d
https://doi.org/10.1137/17m1150037
https://doi.org/10.1137/17m1150037
Publikováno v:
Algorithmica
Algorithmica, Springer Verlag, 2021, 83 (9), pp.2914-2951. ⟨10.1007/s00453-021-00848-1⟩
Algorithmica, Springer Verlag, 2021, 83 (9), pp.2914-2951. ⟨10.1007/s00453-021-00848-1⟩
In the Token Jumping problem we are given a graph G = (V,E) and two independent sets S and T of G, each of size k ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0299dac6957eb2d61f799c56d1d3abc4
http://arxiv.org/abs/2007.01673
http://arxiv.org/abs/2007.01673
Publikováno v:
Journal of Computer and System Sciences. 95:122-131
A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::55e32ea01ac1c7807465c42287d4e859
https://doi.org/10.1016/j.jcss.2018.02.004
https://doi.org/10.1016/j.jcss.2018.02.004
Publikováno v:
SIAM Journal on Discrete Mathematics. 32:1619-1643
A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e. finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subseteq coNP/
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b3aa131e4d413aadad20ee37c6ac95c
https://doi.org/10.1137/17m1136614
https://doi.org/10.1137/17m1136614
In a reconfiguration version of a decision problem 𝒬 the input is an instance of 𝒬 and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73806474daff28ad0dc417b250c00078
http://arxiv.org/abs/1910.00581
http://arxiv.org/abs/1910.00581
Autor:
Amer E. Mouawad, Daniel Lokshtanov
Publikováno v:
ACM Transactions on Algorithms
We settle the complexity of the I ndependent S et R econfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model, the problem is NP-complete.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a104119888042a6be1a0ec4a6bde0706