Publications

• Local Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks. To be published in IEEE Transactions on Mobile Computing, 2008. (With I. Kanj and G. Xia.)

• Computing lightweight spanning subgraphs locally. To be published in Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008), 2008. (With I. Kanj and G. Xia.)

• On Geometric Spanners of Euclidean and Unit Disk Graphs. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), 2008. (With I. Kanj.)
  

•  Strictly Localized Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks. Proceedings of the 4th ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing (DIAL-M-POMC 2007), 2007. (With I. Kanj and G. Xia.)

• Computing Branches Out: On Revitalizing Computing Education. Proceedings of the International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS 2007), Las Vegas, NV, CSREA Press, 22-27, June 2007. (With A. Settle.)

• Quality-of-Service Provisioning via Stochastic Path Selection under Weibullian Link Delays. Proceedings of the Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QShine'07), 2007. (With S. Uludag, A. Kashkanova, and K. Akkaya.)

• Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks. Proceedings of the 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSOR 06), Lecture Notes in Computer Science, 4240:95-106, 2006. (With I. Kanj.)

• A Case for Application-Aware Grid Services. Proceedings of Computing in High Energy Physics (CHEP06), Mumbai, India, Feb 2006. (With G. Garzoglio, A. Baranovski, P. Mhashilkar, and A. Rajendra.)
  

• Bounding the firing synchronization problem on a ring. Theoretical Computer Science, 320(2-3): 213-228, 2004. (With André Berthiaume, Todd Bittner, Amber Settle, and Janos Simon.)

•  A Note on Baker's Algorithm. Technical report, CDM, DePaul University, 2004. (With I. Kanj.)

• Genus Characterizes the Complexity of Graph Problems: Some Tight Results. Journal of Computer and System Sciences, 73, 6:892-907, 2007.
  An early version appeared in proceedings of the 30th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science (LNCS), 2719:845 -856, 2003. (With J. Chen, E. Sedgwick, and G. Xia.)
  

• Improved Parameterized Algorithms for Planar Dominating Set. Proceedings of the 27th Annual Symposium on Mathematical Foundations of Computer Science (MFCS'02), Lecture Notes in Computer Science (LNCS), 2440:399-410, 2002. (With I. Kanj.)
  

• New Bounds for the Firing Squad Problem on a Ring. In proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Carleton Scientific, 17-31, 2002. (With  A. Berthiaume, A. Settle, and J. Simon.)

• Inexpensive d-Dimensional Matchings. Random Structures and Algorithms, 20, 1:50-58, 2002. (With Baei-Shi Huang and Eric Schmutz.)

• An Improved Algorithm for Finding Tree Decompositions of Small Width. In International Journal on Foundations of Computer Science, 11, 3:365--372, 2000. (With B. Reed.)
  An early version was published in the Proceedings of the 25th International Workshop on Graph Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science (LNCS), 1665:148-255, 1999.

• Edge Coloring, Polyhedra and Probability (PhD dissertation). Technical Report CMU-CS-98-176, School of Computer Science, Carnegie Mellon University, 1998.

• Edge Coloring Regular Graphs of High Degree. Discrete Mathematics, 165/166:567-579, 1997. (With B. Reed.)
  

• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Combinatorics, Probability and Computing, 2, 3:271-284, 1993. (With. M Dyer, A. Frieze, R. Kannan, A. Kapoor, and U. Vazirani.)