Selected Publications - Qianping Gu

Journal Papers

• 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