Publications by Ge Xia in Computer Science

Note: All authors appear in alphabetical order in the publications below.
Peer Reviewed Journal Articles

  1. ``Improved Parameterized Upper Bounds for Vertex Cover,''
    Theoretical Computer Science, in press. (with J. Chen, and I.A. Kanj)

    The preliminary version of the paper appeared in the 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.

  2. ``On the Dilation of Delaunay Triangulations of Points in Convex Position,''
    Computational Geometry: Theory and Applications, in press. (With S. Cui and I.A. kanj)

    The preliminary version of the paper appeared in the Proc. 21st Canadian Conference on Computational Geometry (CCCG 2009), pp. 161-164.

  3. ``Separability and Topology Control of Quasi Unit Disk Graphs,''
    Wireless Networks, in press. (with J. Chen, A. Jiang, I.A. Kanj, and F. Zhang)

    The preliminary version of the paper appeared in the Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 2225-2233, 2007.

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

    The preliminary version of the paper appeared in the Proc. 22nd International Symposium on Distributed Computing (DISC 2008), 365-378.

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

    The preliminary version of the paper appeared in the Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, (TAMC 2009) pp. 168-177.

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

    The preliminary version of the paper appeared in the Fourth ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing (DIAL M-POMC 2007).

  7. ``On the Induced Matching Problem,''
    Journal of Computer and System Sciences, in press. (with I.A. Kanj, M.J. Pelsmajer, and M. Schaefer)

    The preliminary version of the paper appeared in the Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 397-408 (STACS 2008).

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

    The preliminary version of the paper appeared in the Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008).

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

    The preliminary version of the paper appeared in the Proceedings of the 10th Italian Conference on Theoretical Computer Science (ICTCS 2007).

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

    Earlier version appeared in Proc. 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), (Springer LNCS 3404), pp. 269-280, Feb. 2005.

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

    Earlier version appeared under the title “Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms,” in Proc. 12th International Computing and Combinatorics Conference (COCOON 2006), (Springer LNCS 4112), pp. 299-308, 2006.

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

    Earlier version appeared in Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (Springer-Verlag LNCS 2719), pp. 845-856, June/July 2003.

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

    Earlier version appeared in Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004) (Springer-Verlag LNCS 3153), pp. 500-512, 2004.

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

    Earlier version appeared under the title``W-Hardness under linear FPT reductions: structural properties and further applications'', in Proc. 11th International Computing and Combinatorics Conference (COCOON 2005), (Springer LNCS 3595), pp. 975-984, Aug. 2005.

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

    Earlier version appeared under the title ``Linear FPT reductions and computational lower bounds'', in Proc. 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 212-221, June 2004.

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

    Earlier version appeared in Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), (Springer-Verlag LNCS 2906), pp. 148-157, Dec. 2003.

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

    Earlier version appeared in Proc. 19th IEEE Conference on Computational Complexity (CCC 2004), pp. 150-160, June 2004.

Peer Reviewed Conference Papers without Journal Versions
  1. ``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). (With I.A. Kanj)

  2. ``On the Small Cycle Transversal of Planar Graphs,''
    Proc. 36th International Workshop on Graph Theoretic (WG 2010). (With Y. Zhang)

  3. ``Kernelization for Cycle Transversal Problems,''
    Proc. 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010). (With Y. Zhang)

  4. ``Local Construction of Spanners in the 3-D Space,''
    Proc. 5th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2009). (With I.A. Kanj and F. Zhang)

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

Other Conference Presentations
  1. ``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. (with I.A. Kanj, and L. Perkovic)

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

Working Papers

 

More papers in other areas.