Yoshio SANO's Papers (sorted by Subject)

Research Topics

• Algorithmic Game Theory


• Matroids on convex geometries (cg-matroids)


• Optimization


• Spectral graph theory


• Competition graphs and their variants
• Competition multigraphs and competition hypergraphs
• Competition numbers and graph structure
• The competition numbers of symmetric graphs


• Graph equation
• Graph decomposition
• Enumerative combinatorics
• Travel groupoid

• Algorithmic Game Theory


• Satoru FUJISHIGE, Yoshio SANO, and Ping ZHAN:
  The random assignment problem with submodular constraints on goods,
  ACM Transactions on Economics and Computation 6 (2018) Article 3, 28 pages.
  doi:10.1145/3175496
  
  See also the following working papers that the above paper is based on.
  
  • Satoru FUJISHIGE, Yoshio SANO, and Ping ZHAN:
    An extended probabilistic serial mechanism to the random assignment problem with multi-unit demands and polymatroidal supplies,
    RIMS-1866, November 2016, 28 pages.
    
  • Satoru FUJISHIGE, Yoshio SANO, and Ping ZHAN:
    A solution to the random assignment problem with a matroidal family of goods,
    RIMS-1852, May 2016, 24 pages.
    


• Yu IGARASHI, Takahito KUNO, and Yoshio SANO:
  On the complexity of the stable marriage problem for restricted instance class,
  RIMS Kokyuroku 1981 (January, 2016) 117-126.
  [Presented at RIMS Workshop ``Optimization for the new age : modeling method and numerical calculation" ]
  http://ci.nii.ac.jp/naid/110010016290
  


• Yu IGARASHI, Takahito KUNO, and Yoshio SANO:
  Improvements on complexity results for the stable marriage with ties and incomplete lists,
  Preprint, October 2016.
  


• Satoru FUJISHIGE, Yoshio SANO, and Ping ZHAN:
  Submodular optimization views on the random assignment problem,
  RIMS-1881, September 2017.
  

• Matroids on convex geometries (cg-matroids)


• Satoru FUJISHIGE, Gleb A. KOSHEVOY, and Yoshio SANO:
  Matroids on convex geometries (cg-matroids),
  Discrete Mathematics 307 (2007) 1936-1950.
  doi:10.1016/j.disc.2006.09.037
  


• Yoshio SANO:
  Rank functions of strict cg-matroids,
  Discrete Mathematics 308 (2008) 4734-4744.
  doi:10.1016/j.disc.2007.08.095
  


• Yoshio SANO:
  Matroids on convex geometries: Subclasses, operations, and optimization,
  Publications of the Research Institute for Mathematical Sciences 47 (2011) 671-703.
  doi:10.2977/PRIMS/48
  


• Yoshio SANO:
  The greedy algorithm for strict cg-matroids,
  Proceedings of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2007) 176-181.
  (See also RIMS-1581: Yoshio SANO: The greedy algorithm for strict cg-matroids, February 2007, 11 pages.)
  


• Yoshio SANO:
  Matroids on convex geometries and the greedy algorithm, (in Japanese)
  RIMS Kokyuroku 1629 (February, 2009) 37-44.
  [Presented at RIMS Workshop ``Mathematical Programming in the 21st Century: Optimization Modeling and Algorithms"]
  http://ci.nii.ac.jp/naid/110007027140
  


• Yoshio SANO:
  Subclasses of cg-matroids,
  Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (2009) 317-322.
  


• Yoshio SANO:
  On the rank functions of H-matroids, (in Japanese)
  RIMS Kokyuroku 1676 (April, 2010) 28-35.
  [Presented at RIMS Workshop ``Mathematical Programming in the 21st Century: Algorithms and Modeling"]
  http://ci.nii.ac.jp/naid/110007573936
  


• Yoshio SANO:
  On the rank functions of $\mathcal{H}$-matroids,
  Journal of Algebra Combinatorics Discrete Structures and Applications 3(1) (2016) 7-11.
  doi:10.13069/jacodesmath.26764, arXiv:1111.2642
  


• Optimization


• Takahito KUNO, Yoshio SANO, and Takahiro TSURUDA:
  Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm,
  Preprint, September 2017. (Revised: February 2018.)
  


• Spectral graph theory


• Taeyoung CHUNG, Jack KOOLEN, Yoshio SANO, and Tetsuji TANIGUCHI:
  The non-bipartite integral graphs with spectral radius three,
  Linear Algebra and its Applications 435 (2011) 2544-2559.
  doi:10.1016/j.laa.2011.04.006, arXiv:1011.6133
  


• Akihiro MUNEMASA, Yoshio SANO, and Tetsuji TANIGUCHI:
  Fat Hoffman graphs with smallest eigenvalue at least $-1-\tau$,
  Ars Mathematica Contemporanea 7 (2014) 247-262.
  Journal Page, arXiv:1111.7284
  


• Akihiro MUNEMASA, Yoshio SANO, and Tetsuji TANIGUCHI:
  Fat Hoffman graphs with smallest eigenvalue greater than $-3$,
  Discrete Applied Mathematics 176 (2014) 78-88.
  doi:10.1016/j.dam.2014.01.008, arXiv:1211.3929
  


• Gary GREAVES, Jack KOOLEN, Akihiro MUNEMASA, Yoshio SANO, and Tetsuji TANIGUCHI:
  Edge-signed graphs with smallest eigenvalue greater than $-2$,
  Journal of Combinatorial Theory, Series B 110 (2015) 90-111.
  doi:10.1016/j.jctb.2014.07.006, arXiv:1309.5178
  


• Akihiro MUNEMASA, Yoshio SANO, and Tetsuji TANIGUCHI:
  On the smallest eigenvalues of the line graphs of some trees,
  Linear Algebra and its Applications 466 (2015) 501-511.
  doi:10.1016/j.laa.2014.10.037, arXiv:1405.3475
  


• Yoshio SANO:
  Fat Hoffman graphs with smallest eigenvalue at least -2.481194304092...,
  Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2015) 417-422.
  


• Competition graphs and their variants


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, Won Jin PARK, and Yoshio SANO:
  The niche graphs of doubly partial orders,
  Congressus Numerantium 195 (2009) 19-32.
  [Presented at 40th Southeastern International Conference on Combinatorics, Graph Theory, and Computing]
  arXiv:0905.3954
  


• Suh-Ryung KIM, Boram PARK, and Yoshio SANO:
  Cycles and p-competition graphs,
  Congressus Numerantium 196 (2009) 23-30.
  [Presented at 40th Southeastern International Conference on Combinatorics, Graph Theory, and Computing]
  arXiv:0905.3942
  


• Yoshio SANO:
  The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$,
  Congressus Numerantium 202 (2010) 187-194.
  [Presented at 41st Southeastern International Conference on Combinatorics, Graph Theory, and Computing]
  arXiv:1006.2631
  


• Boram PARK and Yoshio SANO:
  The phylogeny graphs of doubly partial orders,
  Discussiones Mathematicae Graph Theory 33 (2013) 657-664.
  doi:10.7151/dmgt.1701, arXiv:1103.4540
  


• Kim A. S. FACTOR, Sarah K. MERZ, and Yoshio SANO:
  The (1,2)-step competition number of a graph,
  Congressus Numerantium 215 (2013) 153-161.
  [Presented at 42nd Southeastern International Conference on Combinatorics, Graph Theory, and Computing]
  


• Jeongmi PARK and Yoshio SANO:
  The niche graphs of interval orders,
  Discussiones Mathematicae Graph Theory 34 (2014) 353?359.
  doi:10.7151/dmgt.1741, arXiv:1304.5476
  


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, and Yoshio SANO:
  The competition graphs of oriented complete bipartite graphs,
  Discrete Applied Mathematics 201 (2016) 182-190.
  doi:10.1016/j.dam.2015.07.021
  


• Jihoon CHOI, Kyeong Seok KIM, Suh-Ryung KIM, Jung Yeun LEE, and Yoshio SANO:
  On the competition graphs of d-partial orders,
  Discrete Applied Mathematics 204 (2016) 29-37.
  doi:10.1016/j.dam.2015.11.004, arXiv:1501.03591
  


• Jihoon CHOI, Suh-Ryung KIM, Jung Yeun LEE, and Yoshio SANO:
  On the partial order competition dimensions of chordal graphs,
  Discrete Applied Mathematics 222 (2017) 89-96.
  doi:10.1016/j.dam.2016.08.020, ( arXiv:1601.01188)


• Seung Chul LEE, Jihoon CHOI, Suh-Ryung KIM, and Yoshio SANO:
  On the phylogeny graphs of degree-bounded digraphs,
  Discrete Applied Mathematics 233 (2017) 83-93.
  doi:10.1016/j.dam.2017.07.018, ( arXiv:1611.00246)


• Jihoon CHOI, Suh-Ryung KIM, Jung Yeun LEE, and Yoshio SANO:
  Graphs with partial order competition dimensions greater than three,
  arXiv:1505.00204, May 2015.
  


• Competition multigraphs and competition hypergraphs


• Yoshio SANO:
  Characterizations of competition multigraphs,
  Discrete Applied Mathematics 157 (2009) 2978-2982.
  doi:10.1016/j.dam.2009.04.010
  


• Boram PARK and Yoshio SANO:
  On the hypercompetition numbers of hypergraphs,
  Ars Combinatoria 100 (2011) 151-159.
  arXiv:1005.5622
  


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, and Yoshio SANO:
  The competition hypergraphs of doubly partial orders,
  Discrete Applied Mathematics 165 (2014) 185?191.
  doi:10.1016/j.dam.2012.05.024, arXiv:1111.4375
  


• Jeongmi PARK and Yoshio SANO:
  The double multicompetition number of a multigraph,
  Lecture Notes in Computer Science 8845 (2014) 138-144.
  [Presented at The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013)]
  doi:10.1007/978-3-319-13287-7_12
  


• Jeongmi PARK and Yoshio SANO:
  The double competition hypergraph of a digraph,
  Discrete Applied Mathematics 195 (2015) 110-113.
  doi:10.1016/j.dam.2014.04.001
  


• Yoshio SANO:
  On the hypercompetition numbers of hypergraphs with maximum degree at most two,
  Discussiones Mathematicae Graph Theory 35 (2015) 595-598.
  doi:10.7151/dmgt.1826
  


• Jeongmi PARK and Yoshio SANO:
  The double competition multigraph of a digraph,
  Discrete Mathematics and Theoretical Computer Science 17:2 (2015) 303-310.
  Journal Page, arXiv:1307.5509
  


• Competition numbers and graph structure


• Suh-Ryung KIM, Jung Yeun LEE, and Yoshio SANO:
  The competition number of a graph whose holes do not overlap much,
  Discrete Applied Mathematics 158 (2010) 1456-1460.
  doi:10.1016/j.dam.2010.04.004
  


• Jung Yeun LEE, Suh-Ryung KIM, Seog-Jin KIM, and Yoshio SANO:
  The competition number of a graph with exactly two holes,
  Ars Combinatoria 95 (2010) 45-54.
  arXiv:0909.5302
  
  
• Jung Yeun LEE, Suh-Ryung KIM, Seog-Jin KIM, and Yoshio SANO:
  Graphs having many holes but with small competition numbers,
  Applied Mathematics Letters 24 (2011) 1331-1335.
  doi:10.1016/j.aml.2011.03.003, arXiv:0909.5311
  


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, and Yoshio SANO:
  The competition number of a graph and the dimension of its hole space,
  Applied Mathematics Letters 25 (2012) 638-642.
  doi:10.1016/j.aml.2011.10.003, arXiv:1103.1028
  


• Boram PARK and Yoshio SANO:
  The competition number of a generalized line graph is at most two,
  Discrete Mathematics & Theoretical Computer Science 14:2 (2012) 1-10.
  Journal Page, arXiv:1110.2911
  


• Yoshio SANO:
  A generalization of Opsut's lower bounds for the competition number of a graph,
  Graphs and Combinatorics 29 (2013) 1543-1547.
  doi:10.1007/s00373-012-1188-5, arXiv:1205.4322
  


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, and Yoshio SANO:
  Competitively tight graphs,
  Annals of Combinatorics 17 (2013) 733--741.
  doi:10.1007/s00026-013-0207-4, arXiv:1112.6203
  


• Suh-Ryung KIM, Jung Yeun LEE, Boram PARK, and Yoshio SANO:
  A generalization of Opsut's result on the competition numbers of line graphs,
  Discrete Applied Mathematics 181 (2015) 152-159.
  doi:10.1016/j.dam.2014.10.014
  


• Yoshio SANO:
  On the competition numbers of diamond-free graphs,
  Lecture Notes in Computer Science, to appear.
  [Presented at The 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2015)]
  


• Jung Yeun LEE, Suh-Ryung KIM, and Yoshio SANO:
  The competition number of a graph in which any two holes share at most one edge,
  arXiv:1102.5718, February 2011.
  


• Suh-Ryung KIM, Jung Yeun LEE, and Yoshio SANO:
  Holes and a chordal cut in a graph,
  arXiv:1103.4341, March 2011.
  


• The competition numbers of symmetric graphs


• Suh-Ryung KIM and Yoshio SANO:
  The competition numbers of complete tripartite graphs,
  Discrete Applied Mathematics 156 (2008) 3522-3524.
  doi:10.1016/j.dam.2008.04.009
  


• Boram PARK, Suh-Ryung KIM, and Yoshio SANO:
  The competition numbers of complete multipartite graphs and mutually orthogonal Latin squares,
  Discrete Mathematics 309 (2009) 6464-6469.
  doi:10.1016/j.disc.2009.06.016
  


• Yoshio SANO:
  The competition numbers of regular polyhedra,
  Congressus Numerantium 198 (2009) 211-219.
  [Presented at 40th Southeastern International Conference on Combinatorics, Graph Theory, and Computing]
  arXiv:0905.1763
  


• Suh-Ryung KIM, Boram PARK, and Yoshio SANO:
  The competition numbers of Johnson graphs,
  Discussiones Mathematicae Graph Theory 30 (2010) 449-459.
  doi:10.7151/dmgt.1506
  


• Boram PARK and Yoshio SANO:
  The competition numbers of Hamming graphs with diameter at most three,
  Journal of the Korean Mathematical Society 48 (2011) 691-702.
  doi:10.4134/JKMS.2011.48.4.691, arXiv:1011.2591
  


• Boram PARK and Yoshio SANO:
  The competition numbers of ternary Hamming graphs,
  Applied Mathematics Letters 24 (2011) 1608-1613.
  doi:10.1016/j.aml.2011.04.012, arXiv:1006.2628
  


• Suh-Ryung KIM, Boram PARK, and Yoshio SANO:
  The competition numbers of complete multipartite graphs with many partite sets,
  Discrete Applied Mathematics 160 (2012) 1176-1182.
  doi:10.1016/j.dam.2011.12.017
  


• Suh-Ryung KIM, Boram PARK, and Yoshio SANO:
  The competition number of the complement of a cycle,
  Discrete Applied Mathematics 161 (2013) 1755-1760.
  doi:10.1016/j.dam.2011.10.034
  


• Graph equation


• Seog-Jin KIM, Suh-Ryung KIM, Jung Yeun LEE, Won Jin PARK, and Yoshio SANO:
  Graph equation for line graphs and $m$-step graphs,
  Graphs and Combinatorics 28 (2012) 831-842.
  doi:10.1007/s00373-011-1081-7
  


• Graph decomposition


• Jung Rae CHO, Jeongmi PARK, and Yoshio SANO:
  Edge-disjoint decompositions of complete multipartite graphs into gregarious long cycles,
  Lecture Notes in Computer Science 8296 (2013) 57--63.
  [Presented at Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG 2012)]
  doi:10.1007/978-3-642-45281-9_5


• Enumerative combinatorics


• Yoshio SANO:
  The principal numbers of K. Saito for the types $A_l$, $D_l$ and $E_l$,
  Discrete Mathematics 307 (2007) 2636-2642.
  doi:10.1016/j.disc.2006.11.019
  


• Travel groupoid


• Jung Rae CHO, Jeongmi PARK, and Yoshio SANO:
  Travel groupoids on infinite graphs,
  Czechoslovak Mathematical Journal 64 (2014) 763-766.
  doi:10.1007/s10587-014-0130-9, Journal Page


• Jung Rae CHO, Jeongmi PARK, and Yoshio SANO:
  The non-confusing travel groupoids on a finite connected graph,
  Lecture Notes in Computer Science 8845 (2014) 14-17.
  [Presented at The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013)]
  doi:10.1007/978-3-319-13287-7_2
  


• Jung Rae CHO, Jeongmi PARK, and Yoshio SANO:
  T-neighbor systems and travel groupoids on a graph,
  Graphs and Combinatorics 33 (2017) 1521-1529.
  doi:10.1007/s00373-017-1850-z


• Jung Rae CHO, Jeongmi PARK, and Yoshio SANO:
  T-partition systems and travel groupoids on a graph,
  arXiv:1512.00363, December 2015.