Zobrazeno 1 - 10
of 17
pro vyhledávání: '"Naoto Ohsaka"'
Autor:
Naoto Ohsaka
Publikováno v:
Theoretical Computer Science. 942:253-275
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph $G$ with vertex thresholds $\tau$, consider a dynamic process in which vertex $v$ becomes activated once at least $\tau(v)$ of its neighbors are activated. A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::57b506d1febfcb5e39b5f22f2a41386a
https://doi.org/10.1016/j.tcs.2022.11.036
https://doi.org/10.1016/j.tcs.2022.11.036
Autor:
Tatsuya Matsuoka, Naoto Ohsaka
Publikováno v:
Operations Research Letters. 49:304-309
We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph G = ( V , E ) and a positive semi-definite matrix A indexed by E , a spanning-tree DPP defines a distribution such that we draw S ⊆ E with probability ∝
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b33cbf524f27c1ae918889266a19450b
https://doi.org/10.1016/j.orl.2021.02.004
https://doi.org/10.1016/j.orl.2021.02.004
Autor:
Tatsuya Matsuoka, Naoto Ohsaka
Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Science has been revealing their computational complexity for classical
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f062151c168e02dc6ecca72e96c8241f
Autor:
Tomoya Sakai, Naoto Ohsaka
Publikováno v:
Proceedings of the 2021 SIAM International Conference on Data Mining (SDM) ISBN: 9781611976700
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e91ea8609ce3920e6864672d50316cc5
https://doi.org/10.1137/1.9781611976700.42
https://doi.org/10.1137/1.9781611976700.42
Autor:
Naoto Ohsaka
We consider the problem of counting the number of vertices reachable from each vertex in a digraph $G$, which is equal to computing all the out-degrees of the transitive closure of $G$. The current (theoretically) fastest algorithms run in quadratic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1a289effd6583ea1e557435185e7955c
Autor:
Naoto Ohsaka
Publikováno v:
SIGMOD Conference
Influence maximization is among the most fundamental algorithmic problems in social influence analysis. Over the last decade, a great effort has been devoted to developing efficient algorithms for influence maximization, so that identifying the ``bes
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d358c83e3e53863b241121a767db1cdd
http://arxiv.org/abs/2003.09816
http://arxiv.org/abs/2003.09816
Publikováno v:
Proceedings of the VLDB Endowment. 9:1077-1088
We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks. With this aim, we carefully redesign the data structure of the state-of-the-art sketching method introduced by Borgs et al. , and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8310ab56a5a60e12fa31aaea1775cbb5
https://doi.org/10.14778/2994509.2994525
https://doi.org/10.14778/2994509.2994525
Publikováno v:
SSDBM
Algorithmic problems of computing influence estimation and influence maximization have been actively researched for decades. We developed a novel algorithm, NoSingles, based on the Reverse Influence Sampling method proposed by Borgs et al. in 2013. N
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6b7ae6b97f3ca756dfef5a702ed76d21
https://doi.org/10.1145/3221269.3221291
https://doi.org/10.1145/3221269.3221291
Autor:
Naonori Kakimura, Takuro Fukunaga, Tomohiro Sonobe, Naoto Ohsaka, Sumio Fujita, Ken-ichi Kawarabayashi
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319988085
DEXA (1)
DEXA (1)
We consider and formulate problems of PageRank score boosting motivated by applications such as effective web advertising. More precisely, given a graph and target vertices, one is required to find a fixed-size set of missing edges that maximizes the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::514a162adde44ae7a1b6e758c2e265ec
https://doi.org/10.1007/978-3-319-98809-2_26
https://doi.org/10.1007/978-3-319-98809-2_26