My current interests includes combinatorial optimization, network service and security.

Publication Database (thanks)

Selected publications (sorted by submission date)

Published papers

  1. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``Approximating the minimum k-way cut in a graph via minimum 3-way cuts,'' J. Combinatorial Optimization, vol. 5, no. 4, pp. 397--410 (2001.12). Manuscript versions: gzipped PS file (112K) or PDF file (180K).
  2. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``A note on approximating the survivable network design problem in hypergraphs,'' IEICE Transactions on Information and Systems, vol. E85-D, no. 2, pp. 322--326, (2002.02) Manuscript versions: gzipped PS file (168K) or PDF file (132K).
  3. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``A primal-dual approximation algorithm for the survivable network design problem in hypergraphs,'' Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 275--289 (2003.03). Manuscript versions: gzipped PS file (188K) or PDF file (144K).
  4. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem,'' Information Processing Letters, vol. 86/2, pp. 63--70 (2003.04). Manuscript versions: gzipped PS file (68K) or PDF file (144K), published version is available at ScienceDirect.
  5. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``Greedy splitting algorithms for approximating multiway partition problems,'' Mathematical Programming, vol. 102, no. 1, pp. 167-183 (2005.01). Manuscript versions: gzipped PS file (134K) or PDF file (164K), published version is available at SpringerLink.
  6. Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki, ``On generalized greedy splitting algorithms for multiway partition problems,'' Discrete Applied Mathematics, vol. 143, issues 1-3, pp. 130-143 (2004.09). Manuscript versions: gzipped PS file (187K) or PDF file (480K), published version is available at ScienceDirect.
  7. Keizo Miyata, Shigeru Masuyama, Shin-ichi Nakayama, Liang Zhao, ``NP-hardness Proof and an Approximation Algorithm for the Minimum Vertex Ranking Spanning Tree Problem,'' Discrete Applied Mathematics, vol. 154, issue 16, pp. 2402-2410 (2006.11). Manuscript version: PDF file (180K).
  8. Fujiwara, Hiroki; Wang, Jiexun; Zhao, Liang; Nagamochi, Hiroshi; Akutsu, Tatsuya, ``Enumerating Tree-like Chemical Graphs with Given Path Frequency,'' Journal of Chemical Information and Modeling, 2008, 48 (7), pp. 1345-1357. Available at http://pubs.acs.org/doi/abs/10.1021/ci700385a.

Conference papers (Internatinal, peer-reviewed)

  1. L. Zhao, H. Nagamochi and T.Ibaraki. "Approximating the minimum $k$-way cut in a graph via minimum 3-way cuts", in Proc. ISAAC 1999 (Chennai, India), pp. 373--382, LNCS 1741.
  2. L. Zhao, H. Nagamochi and T. Ibaraki. "A primal-dual approximation algorithm for the survivable network design problem in hypergraph", in Proc. STACS 2001 (Dresden, Germany), pp. 478--489, LNCS 2010.
  3. L. Zhao, H. Nagamochi and T. Ibaraki. "A unified framework for approximating multiway partition problems (extended abstract)", in Proc. ISAAC 2001 (Christchurch, New Zealand), pp. 682--694, LNCS 2223.
  4. K. Katou, L. Zhao, S. Sakazawa and H. Yamamoto. ``An Adaptive Content-Aware Scaling for Receiver-driven Layered Video Multicast", in Proc. ITC-CSCC 2003 (2003.7.7--9, Phoenix Park Hotel, Korea), pp. 904--905. Final versions: gzipped PS file (44K) or PDF file (104K) (2003.07).
  5. L. Zhao and H. Yamamoto. "A Simple Rendering System for Web Presentation", in Proc. ICACT 2004 (2004.2.9-11, Phoenix Park Hotel, Korea), pp. 627--631. Final version: gzipped PS file (332K) or PDF file (200K) (2004.02).
  6. L. Zhao, Y. Inoue and H. Yamamoto. "Delay Reduction for Liner-Search Based Packet Filters", in Proc. ITC-CSCC 2004 (2004/07). Final version: PDF file (64K) (2004-04).
  7. P. Liu, T. Aikawa, S. Miyaji, L. Zhao and H. Yamamoto. "Complexity Reduction in Block Mode Determination for H.264", in Proc. ITC-CSCC 2004 (2004/07). Final version: PDF file (316K) (2004-04).
  8. T. Yokoha, T. Matsumoto, S. Sakazawa, L. Zhao and H. Yamamoto. "On the Subjective Effect of StriMark When Applied to Videos", in Proc. ITC-CSCC 2004 (2004/07). Final version: PDF file (464K) (2004-04).
  9. L. Zhao and H. Yamamoto. "JWebPresenter: A Universal Web Presenting Tool", Linux Conference 2004 (2004/06). Final version: PDF file (272KB).
  10. L. Zhao and H. Yamamoto. "On the Bitmap-Image Based Presenting", IEEE MSE2004, 2004/12, pp. 98--105. Final version: gzipped PS file (73KB) or PDF file (102KB) (2004-12).
  11. L. Zhao and H. Yamamoto. "Multisource Receiver-driven Layered Multicast", IEEE TENCON 2005 (Melbourne, Australia 21-24 Nov. 2005), pp. 1325--1328. Manuscript versions: gzipped PS file (68K) or PDF file (80K). Presentations: PDF file (404K).
  12. Y. Nemoto, S. Sakazawa, L. Zhao and H. Yamamoto. "A Study on Video Scrambling Considering Inter-frame Prediction", IWAIT 2006 (Okinawa, Jan. 9-10, 2006). Final version: PDF file (1907K)
  13. K. Kamata, M. Saito, L. Zhao and H. Yamamoto. "Mobile Accessible Japanese Sign Language Dictionaries over the Internet", Isaac 2006 (Dusseldorf, Germany, July 29th - August 5th 2006). Abstract: PDF file (33K)
  14. Wang Jiexun, Zhao Liang, Hiroshi Nagamochi, Akutsu Tatsuya, ``An Efficient Algorithm for Generation Colored Outerplanar Graphs'', TAMC 2007 (Shanghai, China, May 22-25, 2007).
  15. L. Zhao, A. Shimae and H. Nagamochi. "Linear-tree Rule Structure for Firewall Optimization," CIIT 2007 (Banff, Alberta, Canada, July 2-4, 2007), pp. 67--72. Final paper: gzipped PS file (60K) or PDF file (84K).
  16. L. Zhao, T. Ohshima, H. Nagamochi. ``A* algorithm for the time-dependent shortest path problem,'' WAAC 2008, pp. 36--43. Final paper: PDF (2.9M).
  17. Masahiro Sasaki, Liang Zhao, Hiroshi Nagamochi. ``Security-aware beacon based network monitoring,'' 11th IEEE International Conference on Communication Systems 2008 (Guangzhou, China), pp. 527-531. Manuscript: iccs2008.pdf (116KB).
  18. Y. Ishida, L. Zhao, H. Nagamochi, T. Akutsu. ``Improved Algorithms for Enumerating Tree-like Chemical Graphs with Given Path Frequency,'' GIW 2008 (Gold Coast, Dec. 1-3, 2008). Available at http://www.jsbi.org/modules/journal1/index.php/GI21.html.

Conference (no peer-review)

  1. L. Zhao, H. Nagamochi and T. Ibaraki. "Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts". Technical Report of IEICE. COMP99-19 (1999-6).
  2. L. Zhao, H. Nagamochi and T. Ibaraki. "Greedy splitting: a unified approach for approximating some partition problems". Mathematical optimization theory and its algorithms (Japanese) (Kyoto, 2001). Surikaisekikenkyusho Kokyuroku No. 1241 (2001), 139--147.
  3. L. Zhao, H. Nagamochi and T. Ibaraki. "A primal-dual approximation algorithm for the survivable network design problem in hypergraphs". New developments of the theory of computation and algorithms (Japanese) (Kyoto, 2001). Surikaisekikenkyusho Kokyuroku No. 1205 (2001), 7--12.
  4. L. Zhao and H. Yamamoto, "A Study on Reception Control for RLM with Multiple Sources". ITE annual conference 2005 (2005-08).
  5. Hiroki Fujiwara, Liang Zhao, Hiroshi Nagamochi, Tatsuya Akutsu, ``Enumerating Tree-like Chemical Structures from Feature Vector'', 7th IPSJ SIG BIO (Tokyo, Japan, Dec. 21-22, 2006).
  6. L. Zhao, T. Ohshima, H. Nagamochi, ``A* algorithm for the time-dependent shortest path problem'', 119th IPSJ SIGAL (Tokyo, Japan, May 27, 2008).

Project

Manuscript (unpublished)

Social works

Dissertation

Here comes my dissertation "Approximation Algorithms for Partition and Design Problems in Networks" gzipped PS file (652K) or PDF file (1.6M) (2002.3 Kyoto).

Errata (2004-02-26):