- M. Marzban, Q. Gu and X. Jia,
"New analysis and computational study for the planar connected
dominating set problem",
*Journal of Combinatorial Optimization*, published online, http://link.springer.com/article/10.1007/s10878-015-9871-0 - Z. Bian, Q. Gu, and M. Zhu,
"Practical algorithms for branch-decompositions of planar graphs",
*Discrete Applied Mathematics*, published online, http://dx.doi.org/10.1016/j.dam.2014.12.017 - M. Marzban and Q. Gu,
"Computational study on a PTAS for planar dominating set problem",
*Algorithms*, Vol. 6(1), pp 43-59, 2013. - Q. Gu and H. Tamaki,
"Improved bounds on the planar branchwidth with respect
to the largest grid minor size",
*Algorithmica*, Vol. 64, pp 416-453, 2012. - Q. Gu and H. Tamaki,
"Constant-factor approximations of branch-decomposition and largest
grid minor of planar graphs in $O(n^{1+\epsilon})$ time",
*Theoretical Computer Science,*Vol. 412, pages 4100-4109, 2011. - Z. Bian and Q. Gu,
"Wavelength assignment in multifiber star networks",
*NETWORKS*, Vol. 56(1), pages 30-38, 2010. - M. Marzban, Q. Gu, and X. Jia,
"Computational study on planar dominating set problem",
*Theoretical Computer Science*, Vol. 410, No. 52, pages 5455-5466, 2009. - Z. Bian and Q. Gu,
"1.5-Approximation algorithm for weighted maximum routing
and wavelength assignment on rings",
*Information Processing Letters*, 109, pages 400-404, 2009. - Z. Bian, Q. Gu, and X. Zhou,
"Efficient algorithms for wavelength assignment on trees of rings",
*Discrete Applied Mathematics*, 157, pages 875-889, 2009. - Y. Wang and Q. Gu,
"Minimizing SONET Add-Drop Multiplexers in Optical UPSR
Networks Using the Minimum Number of Wavelengths",
*NETWORKS*, 53(3), pages 276-286, 2009. - Y. Wang and Q. Gu,
"On the complexity and algorithm of grooming regular
traffic in WDM optical networks",
*Journal of Parallel and Distributed Computing (JPDC)*, Vol. 68, No. 6, pages 877-886, 2008. - Y. Wang and Q. Gu,
"Maximum throughput traffic grooming in optical networks",
*Journal of Optical Networking (JON)*, Vol. 7, No. 10, pages 895-904, 2008. - Q. Gu and H. Tamaki,
"Optimal branch-decomposition of planar graphs in
$O(n^3)$ time",
*ACM Trans. on Algorithms*, Vol. 4, No. 3, pages 30:1-30:13, 2008. - Q. Gu and Y. Wang,
"Efficient algorithms for minimum congestion hypergraph
embeddings in a cycle",
*IEEE Trans. on Parallel and Distributed Systems*, Vol. 17, No. 3, pp. 205-214, 2006. - U. Glassaer and Q. Gu,
"Formal description and analysis of a distributed location
service for mobile ad hoc networks",
*Theoretical Computer Science*, Vol. 336 pp. 285-309, 2005. - Q. Gu and S. Peng,
"Multi-hop all-to-all broadcast on WDM optical networks",
*IEEE Trans. on Parallel and Distributed Systems*, Vol. 14 No. 5, pp. 477-486, 2003. - Q. Gu and S. Peng,
"An Efficient Algorithm for $k$-Pairwise Disjoint Paths in Hypercubes",
*Journal of Parallel and Distributed Computing*, Vol. 60, pp. 764-774, 2000. - Q. Gu and H. Tamaki,
"Multicolor Routing in the Undirected Hypercube",
*Discrete Applied Mathematics*, Vol. 100, pp. 169-181, 2000. - Q. Gu and S. Peng,
"Cluster fault tolerant routing in star graphs",
*NETWORKS*, Vol. 35(1), pp. 83-90, 2000. - Q. Gu and S. Peng,
"Unicast in hypercubes with large number of faulty nodes",
*IEEE Trans. on Parallel and Distributed Systems*, Vol. 10, No. 10, pp. 964-975, 1999. -
Q. Gu, S. Peng, and H. Sudborough,
"A 2-Approximation Algorithms
for Genome Rearrangements by
Reversals and Transpositions",
*Theoretical Computer Science*, Vo, 210, pp. 327-339, 1999. -
Q. Gu and S. Peng,
"An efficient algorithm for k-pairwise disjoint paths
in star graphs",
*Information Processing Letters*, Vol. 67, pp. 283-287, 1998. -
Q. Gu and S. Peng,
"Node-to-set and set-to-set cluster fault tolerant routing
in hypercubes",
*Parallel Computing*, Vol. 24, pp. 1245-1261, 1998. -
Q. Gu and H. Tamaki,
"Routing a permutation in the hypercube by two sets
of edge-disjoint paths",
*Journal of Parallel and Distributed Computing*, Vol. 44, pp. 147-152 (1997), -
Q.P. Gu and S. Peng, ``Node-to-set disjoint paths problem in star graphs'',
*Information Processing Letters*, Vol. 62, pp. 201-207, 1997. -
Q. Gu and S. Peng,
"$k$-Pairwise cluster fault tolerant
routing in hypercubes",
*IEEE Trans. on Computers*, Vol. 46, No. 9, pp. 1042-1049 (1997) -
J. Gu, Q. Gu, and D.Z. Du,
"Convergence properties of optimization algorithms
for the SAT problem"
*IEEE Trans. on Computers,*Vol. 45, No. 2, pp. 209-219 (1996) -
Q. Gu and J. Gu,
"Two packet routing algorithms on a mesh-connected computer"
*IEEE Trans. on Parallel and Distributed Systems,*Vol. 6, No. 4, pp. 436-440 (1995) -
Q. Gu and J. Gu,
"Algorithms and average time bounds of sorting on
a mesh connected computer"
*IEEE Trans. on Parallel and Distributed Systems*, Vol. 5, No. 3, pp. 308-315, 1994 -
Q. Gu and A. Maruoka,
"Learning monotone Boolean functions by uniformly
distributed examples"
*SIAM J. on Computing*, Vol. 21, No. 3, pp. 587-599 (1992) -
Q. Gu and A. Maruoka,
"Amplification of bounded depth monotone read-once Boolean formulae"
*SIAM J. on Computing*, Vol. 20, No. 1, pp. 41-55 (1991) -
Q. Gu and A. Maruoka,
"Learning Boolean functions"
*Systems and Computers in Japan*, Vol. 22, No. 1, pp. 1-9 (1991) -
Q. Gu and T. Takaoka,
"A sharper analysis of a parallel algorithm for
the all pairs shortest path problem"
*Parallel Computing*, Vol. 16, pp. 61-67 (1990)

- Q. Gu and G. Xu,
"Constant query time $(1+\epsilon)$-approximate distance oracle for
planar graphs",
*Proc. of the 26th International Symposium on Algorithms and Computation (ISAAC 2015)*, to appear, 2015. - Q. Gu and G. Xu,
"Near-linear time constant-factor approximation algorithm for
branch-decomposition of planar graphs",
*Proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2014)*, LNCS 8747, pp. 238-249, June 2014. - M. Bashir and Q. Gu, "Carving-decomposition based
algorithms for the maximum path coloring problem",
*Proc. of the 2012 International Conference on Communications (ICC2012)*, pp. 3010-3015, June 2012. - C. Wang and Q. Gu, "Computational study on bidimensionality
theory based algorithm for longest path problem",
*Proc. of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011)*, LNCS 7074, pp. 364-373, 2011. - Q. Gu and H. Tamaki,
"Improved bounds on the planar branchwidth with respect to
the largest grid minor size",
*Proc. of the 21st International Symposium on Algorithms and Computation (ISAAC 2010),*LNCS 6507, pages 85-96, 2010. - M. Marzban, Q. Gu, and X. Jia,
"Computational study for planar connected dominating set problem",
*Proc. of the 4th International Conference on Combinatorial Optimization and Applications (COCOA 2010),*LNCS 6509, pages 107-116, 2010. - Q. Gu and N. Imani,
"Connectivity is not a limit for kernelization: Planar connected
dominating set",
*Proc. of the 9th Latin American Symposium on Theoretical Informatics (LATIN 2010),*LNCS 6034, pp. 26-37, 2010. - Q. Gu and H. Tamaki,
"Constant-factor approximations of branch-decomposition and largest
grid minor of planar graphs in $O(n^{1+\epsilon})$ time",
*Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC2009),*LNCS 5878, pp. 984-993, 2009. - M. Marzban, Q. Gu, and X. Jia,
"Computational study on dominating set problem of planar graphs",
*Proc. of the 2nd International Conference on Combinatorial Optimization and Applications (COCOA'08),*LNCS 5165, pages 89-102, 2008. - Z. Bian and Q. Gu,
"Computing branch decomposition of large planar graphs",
*Proc. of the 7th International Workshop on Experimental Algorithms (WEA'08),*LNCS5038, pages 87-100, 2008. - Z. Bian, Q. Gu, M. Marzban, H. Tamaki, and Y. Yoshitake,
"Empirical study on branchwidth and branch decomposition
of planar graphs",
*Proc. of the 2008 SIAM Workshop on Algorithm Engineering and Experiments (ALENEX08)*, pages 152-165, 2008. - Y. Wang and Q. Gu,
"Maximizing throughput for traffic grooming with limited
grooming resources",
*Proc. of the 2007 IEEE Global Telecommunications Conference (GLOBECOM 2007)*, CD-ROM, pp. 2337-2341, 2007. - Z. Bian and Q. Gu,
"Wavelength assignment in multifiber WDM star and
spider networks",
*Proc. of the 2007 IEEE International Conference on Communications (ICC2007)*, CD-ROM, pp. 2430-2435, 2007. - Y. Wang and Q. Gu,
"Grooming of symmetric traffic in unidirectional
SONET/WDM rings",
*Proc. of the 2006 International Conference on Communications (ICC2006)*, CD-ROM, 2407-2414, 2006. - Y. Wang and Q. Gu,
"Efficient algorithms for traffic grooming in
SONET/WDM networks",
*Proc. of the 2006 International Conference on Parallel Processing (ICPP2006)*, pp. 355-362, 2006. - Q. Gu and H. Tamaki,
"Optimal branch-decomposition for planar graphs in O(n^3) time",
*Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP2005)*, LNCS 3580, pp. 373-384, 2005. - Z. Bian, Q. Gu and X. Zhou,
"Tight bounds for wavelength assignment on trees of rings",
*Proc. of the 19th International Parallel and Distributed Processing Symposium (IPDPS2005)*, CD-ROM, 2005. - Z. Bian, Q. Gu and X. Zhou,
"Wavelength assignment on bounded degree trees of rings",
*Proc. of the 10th International Conference on Parallel and Distributed Systems (ICPADS2004)*, pp. 73-80, 2004. - Q. Gu and Yong Wang,
"Efficient algorithm for embedding hypergraphs in a cycle",
*Proc. of the 10th International Conference on High Performance Computing (HiPC03)*, LNCS 2913, pp. 85-94, Dec. 2003 (IEEE TCPP Best Student Paper Award). - Q. Gu,
"On-line permutation routing on WDM all-optical networks",
*Proc. of the 2002 International Conference on Parallel Processing (ICPP02)*, pp. 761-768, Aug. 2002. -
Q. Gu and S. Peng,
``Multi-hop all-to-all broadcast on WDM optical networks'',
*Proc. of the ICPP01 Workshop on Optical Networks*, pp. 291-296, Sept. 2001. -
X. Liu and Q. Gu,
``Multicasts on WDM all-optical
multistage interconnection networks'',
*Proc. of the 2001 International Conference on Parallel and Distributed Systems (ICPADS'01)*, pp. 601-608, June 2001. -
Q. Gu and S. Peng,
``Efficient protocols for permutation routing on all-optical
multistage interconnection networks'',
*Proc. of the 2000 International Conference on Parallel Processing (ICPP'00)*, pp. 513-520, Aug. 2000. - Q. Gu and S. Peng,
"Wavelengths Requirement for Permutation Routing on
All-Optical Multistage Interconnection Networks",
*Proc. of International Parallel and Distributed Processing Symposium (IPDPS 2000)*, pp. 761-768, 2000. - Q. Gu, S. Peng, and Q. Chen,
"Sorting permutations
and its applications in genome analysis",
*Lecture Notes on Mathematics in the Life Science*, Vol. 26, pp. 191-201, 1999. - Q. Gu and S. Peng, "Routing in hypercubes with large number of faults",
*Proc. of the 1998 International Conference on Parallel and Distributed Systems (ICPADS'98)*, pp. 718-724 (Dec. 1998). - Q. Gu and S. Peng,
"Cluster fault tolerant routing in hypercubes",
*Proc. of 1998 International Conference on Parallel Processing (ICPP'98)*, pp. 148-155, 1998. - Q. Gu and H. Tamaki,
"Edge-disjoint routing in the undirected hypercube",
*Proc. of International Symposium on Algorithms and Computations (ISAAC'97)*, LNCS 1350, pp. 72-81, 1997. - Q. Gu and S. Peng,
"Node-to-node cluster fault tolerant routing in hypercubes",
*Proc. of International Symposium on Parallel Algorithms and Networks (ISPAN'97)*, pp. 404-409, 1997. - Q. Gu and Z. Cheng,
"Efficient estimation of diameter for distributed networks",
*Proc. of the 11th Annual International Symposium on High Performance Computing Systems*, pp. 261-268, July 1997. - Z. Cheng and Q. Gu,
"A distributed algorithm for leader election from a partially ordered set",
*Proc. of the 11th Annual International Symposium on High Performance Computing Systems*, pp. 253-260, July 1997. - Q. Gu and H. Tamaki,
"Routing a permutation in the hypercube by two sets
of edge-disjoint paths",
*Proc. of the 10th International Parallel Processing Symposium (IPPS'96)*, pp. 561-567, (1996).Q. Gu and S. Peng, "Algorithms for node-disjoint paths in incomplete star networks",

*Proc. of the 1994 International Conference on Parallel and Distributed Systems (ICPADS'94)*, pp. 296-303 (1994). - Q. Gu and S. Peng,
"$k$-Pairwise cluster fault tolerant routing in hypercubes",
*Proc. of the 5th International Symposium on Algorithms and Computation ISAAC'94*, pp. 345-353, (1994).

Updated Sept. 8, 2015

Back to Prof. Gu's Home Page