3 Search Results for "Nakamura, Kengo"

Document

DOI: 10.4230/LIPIcs.SEA.2023.11

CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints

Authors: Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract

The subgraph counting problem computes the number of subgraphs of a given graph that satisfy some constraints. Among various constraints imposed on a graph, those regarding the connectivity of vertices, such as "these two vertices must be connected," have great importance since they are indispensable for determining various graph substructures, e.g., paths, Steiner trees, and rooted spanning forests. In this view, the subgraph counting problem under connectivity constraints is also important because counting such substructures often corresponds to measuring the importance of a vertex in network infrastructures. However, we must solve the subgraph counting problems multiple times to compute such an importance measure for every vertex. Conventionally, they are solved separately by constructing decision diagrams such as BDD and ZDD for each problem. However, even solving a single subgraph counting is a computationally hard task, preventing us from solving it multiple times in a reasonable time. In this paper, we propose a dynamic programming framework that simultaneously counts subgraphs for every vertex by focusing on similar connectivity constraints. Experimental results show that the proposed method solved multiple subgraph counting problems about 10-20 times faster than the existing approach for many problem settings.

Cite as

Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato. CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2023.11,
  author =	{Nakamura, Kengo and Nishino, Masaaki and Yasuda, Norihito and Minato, Shin-ichi},
  title =	{{CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.11},
  URN =		{urn:nbn:de:0030-drops-183613},
  doi =		{10.4230/LIPIcs.SEA.2023.11},
  annote =	{Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram}
}

Document

DOI: 10.4230/LIPIcs.SEA.2020.22

Variable Shift SDD: A More Succinct Sentential Decision Diagram

Authors: Kengo Nakamura, Shuhei Denzumi, and Masaaki Nishino

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract

The Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions that subsumes the famous Ordered Binary Decision Diagram (OBDD) as a strict subset. SDDs are attracting much attention because they are more succinct than OBDDs, as well as having canonical forms and supporting many useful queries and transformations such as model counting and Apply operation. In this paper, we propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD). The key idea is to create a unique representation for Boolean functions that are equivalent under a specific variable substitution. We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite such succinctness, we show that numerous basic operations that are supported in polytime with SDD are also supported in polytime with VS-SDD. Experiments confirm that VS-SDDs are significantly more succinct than SDDs when applied to classical planning instances, where inherent symmetry exists.

Cite as

Kengo Nakamura, Shuhei Denzumi, and Masaaki Nishino. Variable Shift SDD: A More Succinct Sentential Decision Diagram. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2020.22,
  author =	{Nakamura, Kengo and Denzumi, Shuhei and Nishino, Masaaki},
  title =	{{Variable Shift SDD: A More Succinct Sentential Decision Diagram}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.22},
  URN =		{urn:nbn:de:0030-drops-120968},
  doi =		{10.4230/LIPIcs.SEA.2020.22},
  annote =	{Keywords: Boolean function, Data structure, Sentential decision diagram}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.59

Fully Dynamic Connectivity Oracles under General Vertex Updates

Authors: Kengo Nakamura

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

We study the following dynamic graph problem: given an undirected graph G, we maintain a connectivity oracle between any two vertices in G under any on-line sequence of vertex deletions and insertions with incident edges. We propose two algorithms for this problem: an amortized update time deterministic one and a worst case update time Monte Carlo one. Both of them allow an arbitrary number of new vertices to insert. The update time complexity of the former algorithm is no worse than the existing algorithms, which allow only limited number of vertices to insert. Moreover, for relatively dense graphs, we can expect that the update time bound of the former algorithm meets a lower bound, and that of the latter algorithm can be seen as a substantial improvement of the existing result by introducing randomization.

Cite as

Kengo Nakamura. Fully Dynamic Connectivity Oracles under General Vertex Updates. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nakamura:LIPIcs.ISAAC.2017.59,
  author =	{Nakamura, Kengo},
  title =	{{Fully Dynamic Connectivity Oracles under General Vertex Updates}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.59},
  URN =		{urn:nbn:de:0030-drops-82607},
  doi =		{10.4230/LIPIcs.ISAAC.2017.59},
  annote =	{Keywords: Dynamic Graph, Connectivity, Depth-First Search}
}

Refine by Author
3 Nakamura, Kengo
2 Nishino, Masaaki
1 Denzumi, Shuhei
1 Minato, Shin-ichi
1 Yasuda, Norihito

Refine by Classification
1 Computing methodologies → Knowledge representation and reasoning
1 Mathematics of computing → Graph theory
1 Theory of computation → Data structures design and analysis

Refine by Keyword
2 Connectivity
1 Boolean function
1 Data structure
1 Depth-First Search
1 Dynamic Graph
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2017
1 2020
1 2023