97 citations · 113 across the 13 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
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,…