5 papers
Finding Order-Preserving Subgraphs
Haruya Imamura, Yasuaki Kobayashi, Yota Otachi +5
(Induced) Subgraph Isomorphism and Maximum Common (Induced) Subgraph are fundamental problems in graph pattern matching and similarity computation. In graphs derived from time-seri…
A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki +1
We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all pot…
Gourds: a sliding-block puzzle with turning
Joep Hamersma, Marc van Kreveld, Yushi Uno +1
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1 cells with n pieces, using slidin…
How does object fatness impact the complexity of packing in d dimensions?
Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden
Packing is a classical problem where one is given a set of subsets of Euclidean space called objects, and the goal is to find a maximum size subset of objects that are pairwise non…
On Exploring Temporal Graphs of Small Pathwidth
Hans L. Bodlaender, Tom C. van der Zanden
We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.