Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Tomohiro Koana"'
Publikováno v:
Discrete Applied Mathematics. 324:103-112
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing soc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9f58ae2f81587dfa878d9a1228cfd519
https://doi.org/10.1016/j.dam.2022.09.009
https://doi.org/10.1016/j.dam.2022.09.009
Autor:
André Nichterlein, Tomohiro Koana
Publikováno v:
Discrete Applied Mathematics. 302:198-207
Fox et al. (2020) introduced a new parameter, called c -closure, for a parameterized study of clique enumeration problems. A graph G is c -closed if every pair of vertices with at least c common neighbors is adjacent. The c -closure of G is the small
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9bfc58f1f0158e30be129fe3da67a9b4
https://doi.org/10.1016/j.dam.2021.06.019
https://doi.org/10.1016/j.dam.2021.06.019
Publikováno v:
Autonomous Agents and Multi-Agent Systems. 37
We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5660e9c1cac460f53f53f18b4161a65c
https://doi.org/10.1007/s10458-022-09594-2
https://doi.org/10.1007/s10458-022-09594-2
Publikováno v:
Algorithmic Game Theory ISBN: 9783031157134
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::df8b6c8711e8d69668a3356ad3e99139
https://doi.org/10.1007/978-3-031-15714-1_25
https://doi.org/10.1007/978-3-031-15714-1_25
Publikováno v:
SIAM Journal on Discrete Mathematics; 2022, Vol. 36 Issue 4, p2798-2821, 24p
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number �� [Fox et al., SICOMP 2020] i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::619590663d09eeb2ae830a3c36b2a018
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
WG
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing soc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b8667cc835a1291978f9902a1a05aeab
https://doi.org/10.1007/978-3-030-86838-3_15
https://doi.org/10.1007/978-3-030-86838-3_15
A graph $G$ is weakly $\gamma$-closed if every induced subgraph of $G$ contains one vertex $v$ such that for each non-neighbor $u$ of $v$ it holds that $|N(u)\cap N(v)
Comment: Appeared in ISAAC '20
Comment: Appeared in ISAAC '20
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::347f75ce22eaae9a31ad266a396073b8
http://arxiv.org/abs/2007.05630
http://arxiv.org/abs/2007.05630
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resulting matrix has a Hamming distance within a specified range. We obtain
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5a27d592a1642dc9b9553b5fb0238987
Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For $n$-vertex and $m$-edge graphs, the best known algorithms run in $\widetilde{O}(m\sqrt
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b852fc4b1ca0f12fcdb5e95ad2bb7f38