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)
Conference Papers
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).
Book Chapters and Edited Books
(Editors) Q. Gu, P. Hell, and B. Yang,
Proc. of the 10th International Conference on Algorithm Aspects in
Information and Management (AAIM2014), LNCS 8546, July 2014.
Q. Gu,
"Routing Algorithms on WDM Optical Networks",
Handbook of Applied Algorithms: Solving
Scientific, Engineering, and Practical Problems,
Chapter 18, Pages 509-534, February 2008, (edited by A. Nayak and
I. Stojmenovic) Wiley-IEEE Press.
(Editors) N. Mirenkov, Q. Gu, S. Peng, and S. Sedukhin,
Proc. of The 2nd Aizu International Symposium on Parallel
Algorithms/Architecture Synthesis,
IEEE Computer Society Press, March, 1997.
(Editors) N. Mirenkov, Q. Gu, S. Peng, and S. Sedukhin,
Proc. of The 1st Aizu International Symposium on Parallel
Algorithms/Architecture Synthesis,
IEEE Computer Society Press, March, 1995.