Journal Articles - (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*.
- (with I.A. Kanj)
``On certain geometric properties of the Yao-Yao graphs,''
*J. Comb. Optim.*, 27(1): 78-87, 2014.
- ``The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998,''
*SIAM J. Comput.*, 42(4), 1620–1659, 2013. (Official reprint posted with permission)
- (with J. Chen, I.A. Kanj, J. Meng, and F. Zhang)
``Parameterized top-*K*algorithms.,''
*Theoretical Computer Science*, 470:105-119, 2013.
- (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.
- (with I.A. Kanj)
``Improved local algorithms for spanner construction,''
*Theoretical Computer Science*, 53: 54-64, 2012.
- (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.
- (with Y. Zhang)
``Kernelization for cycle transversal problems,''
*Discrete Applied Mathematics*, 160(7-8): 1224-1231, 2012.
- (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.
- (with Y. Zhang)
``On the Small Cycle Transversal of Planar Graphs,''
*Theoretical Computer Science*, 412(29): 3501-3509, 2011.
- (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.
- (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.
- (with J. Chen, and I.A. Kanj)
``Improved Parameterized Upper Bounds for Vertex Cover,''
*Theoretical Computer Science*, 411(40-42): 3736 - 3756, 2010.
- (with I.A. Kanj and L. Perkovic)
``On Spanners and Lightweight Spanners of Geometric Graphs,''
*SIAM Journal on Computing*, 39(6): 2132-2161, 2010.
- (with J. Chen, and I.A. Kanj)
``On Parameterized Exponential Time Complexity,''
*Theoretical Computer Science*, 410(27-29): 2641-2648, June 2009.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (with J. Chen, X. Huang, and I.A. Kanj)
``Polynomial time approximation schemes and parameterized complexity,''
*Discrete Applied Mathematics*155(2): 180-193, 2007.
- (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.
- (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.
- (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.
- (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 - (With I.A. Kanj)
``Flip Distance is in FPT time O(n+ k * c^k),'' to appear in*STACS 2015*.
- (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.
- (With N. Bonichon, I.A. Kanj, and L. Perkovic)
``There are plane spanners of maximum degree 4,''
*Proceedings of SoCG 2014*: 20.
- (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.
- (with I.A. Kanj)
``When Is Weighted Satisfiability FPT,''
*Proceedings of WADS 2013:*451-462. Full version on arXiv
- (with I.A. Kanj and Binhai Zhu)
``The Radiation Hybrid Map Construction Problem Is FPT,'' ISBRA 2013: 5-16.
- (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*.
- (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.
- ``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.
- (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)
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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).
- (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).
- (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).
- (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.
- (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).
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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.
- (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 - (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.
- (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.
- (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 - (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 - (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. - (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 - (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. - (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 - (With I.A. Kanj and D.M. Thilikos) ``On the Complexity of Weighted Satisfiablility,'' submitted.
- (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.
- (with Donald R. Chambers, Qin Lu, and Ying Quan*) ``Improving assessment of the default risk of single-family mortgages,'' submitted.
Papers in other areas. |