All authors appear in alphabetical order in the publications below.
Peer Reviewed Journal Articles - ``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.
- ``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.
- ``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.
- ``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.
- ``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.
- ``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).
- ``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).
- ``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).
- ``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).
- ``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.
- ``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.
- ``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.
- ``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. - ``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.
- ``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.
- ``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.
- ``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 - ``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)
- ``On the Small Cycle Transversal of Planar Graphs,''
*Proc. 36th International Workshop on Graph Theoretic*(WG 2010). (With Y. Zhang)
- ``Kernelization for Cycle Transversal Problems,''
*Proc. 6th International Conference on Algorithmic Aspects in Information and Management*(AAIM 2010). (With Y. Zhang)
- ``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)
- ``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 - ``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). (with I.A. Kanj, and L. Perkovic)
Working Papers More papers in other areas. |