121 citations · 153 across the 25 of their papers we have counts for
6 papers · 1 filter
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open pro…
Reconfiguration of colorings in triangulations of the sphere
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi +4
In 1973, Fisk proved that any -coloring of a -colorable triangulation of the -sphere can be obtained from any -coloring by a sequence of Kempe-changes. On the other han…
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +6
We initiate the study of -edge-connected orientations of undirected graphs through edge flips for . We prove that in every orientation of an undirected -edge-conne…
Extended Formulations for Sparsity Matroids
Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh +2
We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulati…
Not All Saturated 3-Forests Are Tight
Heidi Gebauer, Anna Gundert, Robin A. Moser +1
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the co…
The Holt-Klee condition for oriented matroids
Komei Fukuda, Sonoko Moriyama, Yoshio Okamoto
Holt and Klee have recently shown that every (generic) LP orientation of the graph of a -polytope satisfies a directed version of the -connectivity property, i.e. there are $…