Robert D. Barish
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Robert D. Barish has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Tetsuo Shibuya
The University of Tokyo
12 shared publications Akira Suyama
University of Tokyo
1 shared publication- Hoi Ping Luk
The NTIS Research Centre, the Faculty of Applied Sciences, Západočeská univerzita v Plzni, Technická 8, 301 00, Plzeň, Czechia (University of West Bohemia in Pilsen), Univerzitní 22, 306 14 Plzeň, Czech Republic
1 shared publication Kam Hang Cheng
1 shared publicationTetsuo Shibuya
Univ Tokyo, Inst Med Sci, Human Genome Ctr, Div Med Data Informat, 4-6-1 Shirokanedai,Minat Ku, Tokyo 1088639, Japan
1 shared publication
Latest Publications
- Open Access
- 16 July 2026
- Published by Elsevier in SSRN Electronic Journal
Dihedral Tilings of the Sphere by Kites and Regular Polygons
In this article, we study the edge-to-edge dihedral tilings of the sphere by kites and regular m-gons with m ≥ 4. All such tilings have been identified and fully classified, using various combinatorial and geometric tools. New phenomena are observed among the tilings.
- 16 July 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessDihedral Tilings of the Sphere by Kites and Regular Polygons
In this article, we study the edge-to-edge dihedral tilings of the sphere by kites and regular m-gons with m ≥ 4. All such tilings have been identified and fully classified, using various combinatorial and geometric tools. New phenomena are observed among the tilings.
- 11 September 2025
- Published by Springer Nature
- p. 45-56
Reconfiguring Planar Perfect Matchings via Bounded Length Alternating Cycles
- 11 September 2025
- Published by Springer Nature
- p. 45-56
Reconfiguring Planar Perfect Matchings via Bounded Length Alternating Cycles
- 11 August 2025
- Published by Springer Nature
- p. 94-103
Counting 2-Factors of 4-Regular Bipartite Graphs is $\#P$-Complete- 11 August 2025
- Published by Springer Nature
- p. 94-103
Counting 2-Factors of 4-Regular Bipartite Graphs is $\#P$-Complete- 18 May 2025
- Published by Springer Nature
- p. 283-298
Packing Dimers to Maximum Occupancy Under Soft-Core Constraints
- 18 May 2025
- Published by Springer Nature
- p. 283-298
Packing Dimers to Maximum Occupancy Under Soft-Core Constraints
- 4 May 2025
- Published by Springer Nature
- p. 170-185
Fair Selection of Clearing Schemes for Kidney Exchange Markets
- 4 May 2025
- Published by Springer Nature
- p. 170-185
Fair Selection of Clearing Schemes for Kidney Exchange Markets
- Open Access
- 1 January 2025
- Published by Information Processing Society of Japan in Journal of Information Processing
- Vol. 33, 1101-1109
Sokoban-style PushPush Games with Unique Solutions
Based on the 1994 Macintosh computer game of the same name, the PushPush variation on Sokoban, which we refer to as PushPush-Storage, is a block pushing puzzle in which the player controls an agent on an integer lattice populated with blocks, where pushing a block causes it to slide to the maximum possible extent without momentum transfer to other blocks, and where the objective is to cover a fixed set of storage sites with unmoving blocks. Here, we consider the problem of designing non-trivial instances of PushPush-Storage puzzles where one can easily quantify how close the player is to finding a given solution. Towards this objective, we show that randomized polynomial time reductions from Boolean satisfiability problems can be used to efficiently construct PushPush-Storage puzzles having unique solutions while also not admitting polynomial time algorithms unless NP =RP. Accordingly, provided a game designer can find a solvable PushPush-Storage puzzle and its solution, the uniqueness of its solution provides a direct means of both quantifying the percentage completion of the puzzle and of determining if a player has become trapped. Finally, we establish that PushPush-Storage puzzles are hard for Ueda and Nagao's class of Another Solution Problem (ASP) function problems.
- 1 January 2025
- Published by Information Processing Society of Japan in Journal of Information Processing
- Vol. 33, 1101-1109
Open AccessSokoban-style PushPush Games with Unique Solutions
Based on the 1994 Macintosh computer game of the same name, the PushPush variation on Sokoban, which we refer to as PushPush-Storage, is a block pushing puzzle in which the player controls an agent on an integer lattice populated with blocks, where pushing a block causes it to slide to the maximum possible extent without momentum transfer to other blocks, and where the objective is to cover a fixed set of storage sites with unmoving blocks. Here, we consider the problem of designing non-trivial instances of PushPush-Storage puzzles where one can easily quantify how close the player is to finding a given solution. Towards this objective, we show that randomized polynomial time reductions from Boolean satisfiability problems can be used to efficiently construct PushPush-Storage puzzles having unique solutions while also not admitting polynomial time algorithms unless NP =RP. Accordingly, provided a game designer can find a solvable PushPush-Storage puzzle and its solution, the uniqueness of its solution provides a direct means of both quantifying the percentage completion of the puzzle and of determining if a player has become trapped. Finally, we establish that PushPush-Storage puzzles are hard for Ueda and Nagao's class of Another Solution Problem (ASP) function problems.
- Open Access
- 1 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1022
String editing under pattern constraints
- 1 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1022
Open AccessString editing under pattern constraints
- Open Access
- 5 May 2024
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 47 (4) , 1-48
Proper colorability of segment intersection graphs
We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-k-DIR, corresponding to intersection graphs of unit length segments lying in at most k directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for $$k = 4$$ that it is NP-complete to decide if a proper 3-coloring exists, and moreover, $$\#P$$ -complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper $$\left( k-1\right) $$ -colorings for every $$k \ge 5$$ . More generally, we establish that the problem of proper 3-coloring an arbitrary graph with m edges can be reduced in $${\mathcal {O}}\left( m^2\right) $$ time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no $$2^{o\left( \sqrt{n}\right) }$$ time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no $$2^{o\left( \sqrt{n}\right) }$$ time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an NP-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph.- 5 May 2024
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 47 (4) , 1-48
Open AccessProper colorability of segment intersection graphs
We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-k-DIR, corresponding to intersection graphs of unit length segments lying in at most k directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for $$k = 4$$ that it is NP-complete to decide if a proper 3-coloring exists, and moreover, $$\#P$$ -complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper $$\left( k-1\right) $$ -colorings for every $$k \ge 5$$ . More generally, we establish that the problem of proper 3-coloring an arbitrary graph with m edges can be reduced in $${\mathcal {O}}\left( m^2\right) $$ time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no $$2^{o\left( \sqrt{n}\right) }$$ time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no $$2^{o\left( \sqrt{n}\right) }$$ time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an NP-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph. - 3 May 2024
- Published by Springer Nature
- p. 272-283
Counting on Rainbow k-Connections
- Open Access
- 13 April 2024
- Published by Springer Nature in Optimization Letters
- Vol. 19 (1) , 151-168
Affine optimal k-proper connected edge colorings
We introduce affine optimal k-proper connected edge colorings as a variation on Fujita’s notion of optimal k-proper connected colorings (Fujita in Optim Lett 14(6):1371–1380, 2020. https://doi.org/10.1007/s11590-019-01442-9) with applications to the frequency assignment problem. Here, for a simple undirected graph G with edge set $$E_G$$ , such a coloring corresponds to a decomposition of $$E_G$$ into color classes $$C_1, C_2, \ldots , C_n$$ , with associated weights $$w_1, w_2, \ldots , w_n$$ , minimizing a specified affine function $${\mathcal {A}}\, {:=}\,\sum _{i=1}^{n} \left( w_i \cdot |C_i|\right)$$ , while also ensuring the existence of k vertex disjoint proper paths (i.e., simple paths with no two adjacent edges in the same color class) between all pairs of vertices. In this context, we define $$\zeta _{{\mathcal {A}}}^k(G)$$ as the minimum possible value of $${\mathcal {A}}$$ under a k-proper connectivity requirement. For any fixed number of color classes, we show that computing $$\zeta _{{\mathcal {A}}}^k(G)$$ is treewidth fixed parameter tractable. However, we also show that determining $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ with the affine function $${\mathcal {A}}^{\prime } \, {:=}\,0 \cdot |C_1| + |C_2|$$ is NP-hard for 2-connected planar graphs in the case where $$k = 1$$ , cubic 3-connected planar graphs for $$k = 2$$ , and k-connected graphs $$\forall k \ge 3$$ . We also show that no fully polynomial-time randomized approximation scheme can exist for approximating $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ under any of the aforementioned constraints unless $$NP=RP$$ .- 13 April 2024
- Published by Springer Nature in Optimization Letters
- Vol. 19 (1) , 151-168
Open AccessAffine optimal k-proper connected edge colorings
We introduce affine optimal k-proper connected edge colorings as a variation on Fujita’s notion of optimal k-proper connected colorings (Fujita in Optim Lett 14(6):1371–1380, 2020. https://doi.org/10.1007/s11590-019-01442-9) with applications to the frequency assignment problem. Here, for a simple undirected graph G with edge set $$E_G$$ , such a coloring corresponds to a decomposition of $$E_G$$ into color classes $$C_1, C_2, \ldots , C_n$$ , with associated weights $$w_1, w_2, \ldots , w_n$$ , minimizing a specified affine function $${\mathcal {A}}\, {:=}\,\sum _{i=1}^{n} \left( w_i \cdot |C_i|\right)$$ , while also ensuring the existence of k vertex disjoint proper paths (i.e., simple paths with no two adjacent edges in the same color class) between all pairs of vertices. In this context, we define $$\zeta _{{\mathcal {A}}}^k(G)$$ as the minimum possible value of $${\mathcal {A}}$$ under a k-proper connectivity requirement. For any fixed number of color classes, we show that computing $$\zeta _{{\mathcal {A}}}^k(G)$$ is treewidth fixed parameter tractable. However, we also show that determining $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ with the affine function $${\mathcal {A}}^{\prime } \, {:=}\,0 \cdot |C_1| + |C_2|$$ is NP-hard for 2-connected planar graphs in the case where $$k = 1$$ , cubic 3-connected planar graphs for $$k = 2$$ , and k-connected graphs $$\forall k \ge 3$$ . We also show that no fully polynomial-time randomized approximation scheme can exist for approximating $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ under any of the aforementioned constraints unless $$NP=RP$$ .