97 citations · 113 across the 13 of their papers we have counts for
15 papers
Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs
Jun Kawahara, Toshiki Saitoh, Hirokazu Takeda +2
Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse searc…
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
Takehiro Ito, Jun Kawahara, Yu Nakahata +4
This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In g…
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama +3
In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtrack…
Reallocation Problems with Minimum Completion Time
Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino +1
Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce…
The Essential Role of Empirical Validation in Legislative Redistricting Simulation
Benjamin Fifield, Kosuke Imai, Jun Kawahara +1
As granular data about elections and voters become available, redistricting simulation methods are playing an increasingly important role when legislatures adopt redistricting plan…
Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration
Yu Nakahata, Jun Kawahara, Takashi Horiyama +1
Given graphs and , we propose a method to implicitly enumerate topological-minor-embeddings of in using decision diagrams. We show a useful application of our method…
Decomposing a Graph into Unigraphs
Takashi Horiyama, Jun Kawahara, Shin-ichi Minato +1
Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. There are many subclasses of unigraphs such as threshold graphs, split matrogenic graphs, m…
Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams
Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki +1
We propose a general method performed over multivalued decision diagrams that enumerates all subgraphs of an input graph that are characterized by input forbidden induced subgraphs…
Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams
Yu Nakahata, Jun Kawahara, Shoji Kasahara
Partitioning a graph into balanced components is important for several applications. For multi-objective problems, it is useful not only to find one solution but also to enumerate…
The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka
The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colo…
Effect of Bitcoin fee on transaction-confirmation process
Shoji Kasahara, Jun Kawahara
In Bitcoin system, transactions are prioritized according to transaction fees. Transactions without fees are given low priority and likely to wait for confirmation. Because the dem…
An improved lower bound for one-dimensional online unit clustering
Jun Kawahara, Koji M. Kobayashi
The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: "Points" are given on…
Better Bounds for Online -Frame Throughput Maximization in Network Switches
Jun Kawahara, Koji M. Kobayashi, Shuichi Miyazaki
We consider a variant of the online buffer management problem in network switches, called the -frame throughput maximization problem (-FTM). This problem models the situation…
Tight Analysis of Priority Queuing Policy for Egress Traffic
Jun Kawahara, Koji M. Kobayashi, Tomotaka Maeda
Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper,…