Publications by Ge Xia in Computer Science


An up-to-date list of publications is on DBLP

 

The following is an outdated list of publications (All authors appear in alphabetical order in the publications below.)


Journal Articles

  1. (With L. Barba, P. Bose, M. Damian, R. Fagerberg, W.L. Keng, J. O'Rourke, A. van Renssen, P. Taslakian, and S. Verdonschot)
    ``New and improved spanning ratios for Yao graphs,''
    to appear in Journal of Computational Geometry.

  2. (with I.A. Kanj)
    ``On certain geometric properties of the Yao-Yao graphs,''
    J. Comb. Optim., 27(1): 78-87, 2014.

  3. ``The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998,''
    SIAM J. Comput., 42(4), 16201659, 2013. (Official reprint posted with permission)

  4. (with J. Chen, I.A. Kanj, J. Meng, and F. Zhang)
    ``Parameterized top-K algorithms.,''
    Theoretical Computer Science, 470:105-119, 2013.

  5. (with C. Ashby, D. Johnson, K. Walker, I.A. Kanj, and X. Huang)
    ``New enumeration algorithm for protein structure comparison and classification,''
    BMC Genomics, 14(Suppl 2):S1, 2013.

  6. (with I.A. Kanj)
    ``Improved local algorithms for spanner construction,''
    Theoretical Computer Science, 53: 54-64, 2012.

  7. (with J. Jenkins*, I.A. Kanj, and F. Zhang)
    ``Local Construction of Spanners in the 3-D Space,''
    IEEE Transactions on Mobile Computing, 11(7): 1140-1150, 2012.

  8. (with Y. Zhang)
    ``Kernelization for cycle transversal problems,''
    Discrete Applied Mathematics, 160(7-8): 1224-1231, 2012.

  9. (with I.A. Kanj, M.J. Pelsmajer, and M. Schaefer)
    ``On the Induced Matching Problem,''
    Journal of Computer and System Sciences, 77(6): 1058-1070, 2011.

  10. (with Y. Zhang)
    ``On the Small Cycle Transversal of Planar Graphs,''
    Theoretical Computer Science, 412(29): 3501-3509, 2011.

  11. (with S. Cui and I.A. Kanj)
    ``On the Dilation of Delaunay Triangulations of Points in Convex Position,''
    Computational Geometry: Theory and Applications, 44(2):104-109, February 2011.

  12. (with J. Chen, A. Jiang, I.A. Kanj, and F. Zhang)
    ``Separability and Topology Control of Quasi Unit Disk Graphs,''
    Wireless Networks, 17(1): 53-67, 2011.

  13. (with J. Chen, and I.A. Kanj)
    ``Improved Parameterized Upper Bounds for Vertex Cover,''
    Theoretical Computer Science, 411(40-42): 3736 - 3756, 2010.

  14. (with I.A. Kanj and L. Perkovic)
    ``On Spanners and Lightweight Spanners of Geometric Graphs,''
    SIAM Journal on Computing, 39(6): 2132-2161, 2010.

  15. (with J. Chen, and I.A. Kanj)
    ``On Parameterized Exponential Time Complexity,''
    Theoretical Computer Science, 410(27-29): 2641-2648, June 2009.

  16. (with I.A. Kanj, and L. Perkovic)
    ``Local Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks,''
    IEEE Transactions on Mobile Computing, 8(4): 460-474, April 2009.

  17. (with J. Chen, I.A. Kanj, J. Meng, and F. Zhang)
    ``On the Pseudo-Achromatic Number Problem,''
    Theoretical Computer Science, 410(8-10): 818-829, March 2009.

  18. (with I.A. Kanj, L. Nakhleh, and C. Than)
    ``Seeing the trees and their branches in the network is hard,''
    Theoretical Computer Science, 401(1-3): 153-164, 2008.

  19. (with I. Kanj, and L. Nakhleh)
    ``The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms,''
    Algorithmica, 51(2): 99–128, June, 2008.

  20. (with J. Chen, H. Fernau, and I.A. Kanj)
    ``Parametric duality and kernelization: lower bounds and upper bounds on kernel size,''
    SIAM Journal on Computing, 37(4): 1077-1106, November 2007.

  21. (with J. Chen, I.A. Kanj, L. Perkovic, and E. Sedgwick)
    ``Genus characterizes the complexity of graph problems: some tight results,''
    Journal of Computer and System Sceiences, 73(6): 892-907, September 2007.

  22. (with J. Chen, X. Huang, and I.A. Kanj)
    ``Polynomial time approximation schemes and parameterized complexity,''
    Discrete Applied Mathematics 155(2): 180-193, 2007.

  23. (with J. Chen, X. Huang, and I.A. Kanj)
    ``On the computational hardness based on linear FPT-reductions,''
    Journal of Combinatorial Optimization 11(2): 231-247, 2006.

  24. (with J. Chen, X. Huang, and I.A. Kanj)
    ``Strong Computational Lower Bounds via Parameterized Complexity,''
    Journal of Computer and System Sceiences 72(8): 1346-1367, 2006.

  25. (with J. Chen, and I.A. Kanj)
    ``Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems,''
    Algorithmica, 43(4): 245-273, December 2005.

  26. (with J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, and I.A. Kanj)
    ``Tight lower bounds for parameterized NP-hard problems,''
    Information and Computation, 201(2): 216-231, September 2005.


Conference Papers
  1. (With I.A. Kanj)
    ``Flip Distance is in FPT time O(n+ k * c^k),''
    to appear in STACS 2015.

  2. (With I.A. Kanj, G. Lin, T. Liu, W.n Tong, J. Xu, B. Yang, F. Zhang, P. Zhang, B. Zhu)
    ``Algorithms for Cut Problems on Trees,''
    Proceedings of COCOA 2014: 283-298.

  3. (With N. Bonichon, I.A. Kanj, and L. Perkovic)
    ``There are plane spanners of maximum degree 4,''
    Proceedings of SoCG 2014: 20.

  4. (With L. Barba, P. Bose, M. Damian, R. Fagerberg, W.L. Keng, J. O'Rourke, A. van Renssen, P. Taslakian, and S. Verdonschot)
    ``New and improved spanning ratios for Yao graphs,''
    Proceedings of SoCG 2014: 30.

  5. (with I.A. Kanj)
    ``When Is Weighted Satisfiability FPT,''
    Proceedings of WADS 2013: 451-462.
    Full version on arXiv

  6. (with I.A. Kanj and Binhai Zhu)
    ``The Radiation Hybrid Map Construction Problem Is FPT,''
    ISBRA 2013: 5-16.

  7. (with C. Ashby, X. Huang, D. Johnson, I.A. Kanj, and K. Walker)
    ``New Enumeration Algorithm for Protein Structure Comparison and Classification,''
    Proceedings of ISCB-Asia/SCCG 2012.

  8. (with I.A. Kanj)
    ``On certain geometric properties of the Yao-Yao graphs,''
    Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012). pp. 223-233.

  9. ``Improved Upper Bound on the Stretch Factor of Delaunay Triangulations,''
    Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG 2011), pp. 264-273.
    Full version ``The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998,'' available on arXiv.

  10. (with L. Zhang)
    ``Toward the Tight Bound of the Stretch Factor of Delaunay Triangulations,''
    Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011). (with Liang Zhang)

  11. (with I.A. Kanj)
    ``Local Algorithms for Constructing Spanners: Improved Bounds,''
    Proc. 36th 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2010), LNCS 6451, pp. 1–15, 2010.

  12. (with Y. Zhang)
    ``Kernelization for Cycle Transversal Problems,''
    Proc. 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010), LNCS 6124, pp. 293–303, 2010.

  13. (with Y. Zhang)
    ``On the Small Cycle Transversal of Planar Graphs,''
    Proc. 36th International Workshop on Graph Theoretic (WG 2010), LNCS 6410, pp. 112–122, 2010.

  14. (with J. Jenkins*, I.A. Kanj, and F. Zhang)
    ``Local Construction of Spanners in the 3-D Space,''
    Proc. 5th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2009), pp. 315-328.

  15. (with S. Cui and I.A. Kanj)
    ``On the Dilation of Delaunay Triangulations of Points in Convex Position,''
    Proc. 21st Canadian Conference on Computational Geometry (CCCG 2009), pp. 161-164.

  16. (with J. Chen, and I.A. Kanj)
    ``On Parameterized Exponential Time Complexity,''
    Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, (TAMC 2009) pp. 168-177.

  17. (with I.A. Kanj and L. Perkovic)
    ``On Spanners and Lightweight Spanners of Geometric Graphs,''
    Proc. 22nd International Symposium on Distributed Computing (DISC 2008), 365-378.

  18. (with I.A. Kanj, M.J. Pelsmajer, and M. Schaefer)
    ``On the Induced Matching Problem,''
    Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 397-408 (STACS 2008).

  19. (with J. Chen, I.A. Kanj, J. Meng, and F. Zhang)
    ``On the Pseudo-Achromatic Number Problem,''
    Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008).

  20. (with I.A. Kanj, and L. Perkovic)
    ``Local Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks,''
    Fourth ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing (DIAL M-POMC 2007).

  21. (with J. Chen, A. Jiang, I.A. Kanj, and F. Zhang)
    ``Separability and Topology Control of Quasi Unit Disk Graphs,''
    Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 2225-2233, 2007.

  22. (with I.A. Kanj, L. Nakhleh, and C. Than)
    ``Seeing the trees and their branches in the network is hard,''
    Proceedings of the 10th Italian Conference on Theoretical Computer Science (ICTCS 2007).

  23. (with J. Chen, I.A. Kanj, J. Meng, and F. Zhang)
    ``On the Effective Enumerability of NP Problems,''
    Proc. 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), (Springer LNCS 4169), pp. 215-226, 2006.

  24. (with J. Chen, and I.A. Kanj)
    ``Improved Parameterized Upper Bounds for Vertex Cover,''
    Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006) (Springer LNCS 4162), pp. 238-249, 2006. Stará Lesná, Slovakia, August 28-September 1, 2006.

  25. (with I. Kanj, and L. Nakhleh)
    ``Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms,''
    Proc. 12th International Computing and Combinatorics Conference (COCOON 2006), (Springer LNCS 4112), pp. 299-308, 2006.

  26. (with J. Chen, H. Fernau, and I.A. Kanj)
    ``Parametric duality and kernelization: lower bounds and upper bounds on kernel size,''
    Proc. 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), (Springer LNCS 3404), pp. 269-280, Feb. 2005.

  27. (with J. Chen, X. Huang, and I.A. Kanj)
    ``W-Hardness under linear FPT reductions: structural properties and further applications,''
    Proc. 11th International Computing and Combinatorics Conference (COCOON 2005), (Springer LNCS 3595), pp. 975-984, Aug. 2005.

  28. (with J. Chen, X. Huang, and I.A. Kanj)
    ``Linear FPT reductions and computational lower bounds,''
    Proc. 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 212-221, June 2004.

  29. (with J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, and I.A. Kanj)
    ``Tight lower bounds for parameterized NP-hard problems,''
    Proc. 19th IEEE Conference on Computational Complexity (CCC 2004), pp. 150-160, June 2004.

  30. (with J. Chen, X. Huang, and I.A. Kanj)
    ``Polynomial time approximation schemes and parameterized complexity,''
    Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004) (Springer-Verlag LNCS 3153), pp. 500-512, 2004.

  31. (with J. Chen, I.A. Kanj, L. Perkovic, and E. Sedgwick)
    ``Genus characterizes the complexity of graph problems: some tight results,''
    Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (Springer-Verlag LNCS 2719), pp. 845-856, June/July 2003.

  32. (with J. Chen, and I.A. Kanj)
    ``Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems,''
    Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), (Springer-Verlag LNCS 2906), pp. 148-157, Dec. 2003.


Other Conference Presentations
  1. (with L. Zhang)
    ``Improved Lower Bound for the Stretch Factor of Delaunay Triangulations,''
    poster in 20th Fall Workshop on Computational and Combinatorial Geometry (FWCG 2010), SUNY Stony Brook.

  2. (with I.A. Kanj, and L. Perkovic)
    ``An Optimal Localized Approximation Scheme for Euclidean MST,''
    extended abstract in 17th Fall Workshop on Computational and Combinatorial Geometry (FWCG 2007), IBM Watson Research Center, Hawthorne, NY, Nov 9-10, 2007.

  3. (with I.A. Kanj, and L. Perkovic)
    ``Strictly Localized Construction of Planar Bounded-Degree Spanners of Unit Disk Graphs,''
    in Second Workshop on Locality Preserving Distributed Computing Methods (LOCALITY 2007).


Book Chapters
  1. (with Jianer Chen) ``Complexity issues on PTAS,'' a book chapter of Handbook of Combinatorial Optimization, Second Edition, P. Pardalos, D.-Z. Du, and R. Graham, eds., Springer pp. 723-746, 2013.

Other Conference Presentations
  1. (with I.A. Kanj and L. Perkovic) ``An optimal localized approximation scheme for Euclidean MST,'' Extended abstract in Proceedings of the 17th Fall Workshop on Computational and Combinatorial Geometry (FWCG 2007), IBM Watson Research Center, Hawthorne, NY, Nov 9--10, 2007.
  2. (with I.A. Kanj and L. Perkovic) ``Strictly localized construction of planar bounded-degree spanners of unit disk graphs,'' in 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY 2007).

Posters
  1. (with L. Zhang*) ``Lower bound for the spanning ratio of Delaunay triangulation,'' Poster in Proceedings of the 20th Annual Fall Workshop on Computational Geometry (FWCG 2010), Stony Brook University, Stony Brook, NY, Oct 29-30, 2010.
  2. (with T. Haruguchi*, J. LoBue*, J. Pierce*, and D. Roberson*) ``On the parameterized complexity of independent set,'' Poster presented at the AMS/MAA Joint Mathematics Meetings, New Orleans, LA, January 5--8, 2007.

Work in Progress
  1. (With I.A. Kanj and D.M. Thilikos) ``On the Complexity of Weighted Satisfiablility,'' submitted.
  2. (with I.A. Kanj, G. Lin, T. Liu, W. Tong, J. Xu, B. Yang, F. Zhang, P. Zhang, and B. Zhu) ``Algorithms for Cut Problems on Trees,'' submitted.
  3. (with Donald R. Chambers, Qin Lu, and Ying Quan*) ``Improving assessment of the default risk of single-family mortgages,'' submitted.

Papers in other areas.