Hristo Nikolov Djidjev

 

Research Interests

• Combinatorial algorithms: shortest paths, graph partitioning, combinatorial optimization
• Network analysis: data mining, community structure detection, network visualization
• Sensor networks: coverage, placement, optimization
• Algorithm engineering: efficient implementation of combinatorial algorithms

Professional Experience

Technical staff member, Los Alamos National Lab, Los Alamos, 2005-current
Research Adjunct Professor, Carleton University, Ottawa, 1990-current
Senior Lecturer, University of Warwick, 1998-2002
Assistant Professor and Research Scientist, Rice University, 1992-1998
Visiting Professor, Duke University, 1990
Visiting Professor, MIT, 1989
Research Associate and Senior Research Associate, Center of Informatics and Computer Technology, Bulgarian Academy of Sciences, 1985-1991

Education

Ph. D. in Computer Science, Sofia University
M. Sc. in Mathematics, Sofia University

Professional Activities

Editorial Service:

• Member of the standing committee and editor of Parallel Processing Letters
• Editor of Discrete Mathematics and Theoretical Computer Science
• Chairman of the organizing committee of the international workshop on Optimal Algorithms
• Editor of vol. 401 of Lecture Notes of Computer Science
• Reviewer for Algorithmica, Computational Geometry: Theory and Applications, Journal of Algorithms, Information and Computation, Information Processing Letters, Networks, SIAM Journal on Computing, SIAM Journal of Discrete Mathematics, Theoretical Computer Science, National Science Foundation, and others

University  and Departmental Service:

• Member of the Library Committee
• Member of the Environmental Strategic Planning Committee
• Chairman of the Teaching Issues Committee
• Chairman of the Colloquium Committee
• Member of the Undergraduate Committee
• Chairman of Automata or Algorithms qualifying exams
• Speaker at Corporate Affiliates Meetings
• Coordinator for the Workshop on Algorithmic Research in the Midsouthwest

Awards

• EPSRC Award GR/M60750: Algorithms and tools for graph partitioning, 1999-2002.
• Future and Emerging Technologies programme of the EU (ALCOM-FT) contract number IST-1999-14186 (as a member of the Warwick team), 2000-2003.
• RTDF Award 98/99-0140 Algorithms and tools for web searching, with M. Joy and M. Luck, 1999-2000.
• EPA Award R82-5207-010: Partitioning algorithms and their application to massively parallel computations of multiphase fluid flows in porous media, with R. Ewing, R. Lazarov, and M. Vardi, 1996-2000.
• NSF Award CCR-9409181 RIA: Efficient algorithms for special classes of graphs, 1994-1997.

Publications

Refereed Journal and Conference Papers

• H. Djidjev, A linear algorithm for finding a maximal planar subgraph, SIAM Journal of Discrete Mathematics, 2006 (to appear).
• Hristo Djidjev, Efficient computation of minimum exposure paths in a sensor network field, Proc. IEEE International Conference on Distributed Computing in Sensor Networks (DCOSS), in Lecture Notes in Computer Science vol. 4549, LA-UR-07-0591, 2007.
• Hristo Djidjev, Imrich Vrto, Crossing Numbers and Cutwidths, J. Graph Algorithms and Applications, vol. 7, no. 3, pp. 245--251, 2003.
• Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo and Anil Maheshwari, Partitioning Planar Graphs with Costs and Weights, Proc. of 2nd Workshop on Algorithm Engineering and Experiments (ALENEX'02), San Francisco, 2002.
• H. Djidjev, I. Vrto, An Improved Lower Bound for Crossing Numbers, Proc. 9th Intl. Symp. on Graph Drawing, Lecture Notes in Computer Science 2265, Springer Verlag, Berlin, 2002, pp. 96-101.
• H. Djidjev, M. Joy, A. Twigg, Collecting and Classifying Information from the WWW, Proceedings of SSGRR'01 (invited), Rome, 2001.
• H. Djidjev, Finding shortest cycles in networks of bounded genus, International Workshop on Interconnection Networks (IWIN'01), Vall de Nuria, 2001.
• H. Djidjev, Force-directed methods for smoothing unstructured triangular and tetrahedral meshes, Proceedings of the 9th International Meshing Roundtable, October 2-5, 2000, New Orleans, pp. 395-406.
• H. Djidjev, Computing the girth of a planar graph, International Colloquium on Automata, Languages and Programming (ICALP'00), Lecture Notes in Computer Science, vol. 1853, 2000, pp. 821-831.
• H. Djidjev, Partitioning planar graphs with vertex costs: algorithms and applications, Algorithmica, vol. 28 (2000), pp. 51-75.
• L. Aleksandrov and H. Djidjev, A Dynamic Algorithm for Maintaining Graph Partitions, Scandinavian Workshop on Algorithm Theory (SWAT'00), Lecture Notes in Computer Science, vol. 1851, 2000, pp. 71-82.
• H. Djidjev, Force-directed methods for mesh improvement, Proc. of 2nd Workshop on Algorithm Engineering and Experiments (ALENEX 00), 2000, pp. 29-42.
• H. Djidjev, G. Pantziou and C. Zaroliagis, Improved Algorithms for Dynamic Shortest Paths, Algorithmica, vol. 28:4, 2000, pp. 367-389.
•   L. Alexandrov, H. N. Djidjev, J.-R. Sack, Finding a shortest central link segment of a simple polygon in O(n log n) time, International Journal of Computational Geometry and Applications, vol. 10, No. 2, 2000, pp. 157-188.
•   H. N. Djidjev, J.R. Gilbert, Separators in graphs with negative or multiple vertex weights, Algorithmica, vol. 23 (1999), pp. 57-71.
• L.G. Aleksandrov, H.N. Djidjev, Maintaining Partitions of Dynamic Planar Meshes, Proceedings of the Canadian Conference on Computational Geometry (CCCG'98), 1998, pp. 84-85.
•   H. N. Djidjev, S. M. Venkatesan, Reduced constants for simple cycle graph separation, Acta Informatica, vol. 34 (1998), pp. 231-243.
• H. N. Djidjev, Weighted graph separators and their application, European Symposium on Algorithms (ESA'97), Lecture Notes in Computer Science, 1997, vol. 1284, pp. 130-143.
•   H. N. Djidjev, Efficient Algorithms for Shortest Path Queries in Planar Digraphs, in Proc. 22nd Workshop on Graph-Theoretic Concepts in Computer Science (WG '96), Lecture Notes in Computer Science, Springer-Verlag, 1996, pp. 151-165.
•   L. Aleksandrov and H. Djidjev. Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus. SIAM Journal of Discrete Mathematics, vol. 9 (1996), pp. 129-150.
•   H. Djidjev, A Linear Algorithm for the Maximal Planar Subgraph Problem, in Proceedings of WADS'95, Lecture Notes in Computer Science, vol. 955, pp. 369-380, Springer-Verlag, 1995.
•   H. Djidjev, G. Pantziou and C. Zaroliagis, Fast Algorithms for Maintaining Shortest Paths in Outerplanar and Planar Digraphs, Proc. 10th Conf. on Fundamentals of Computation Theory (FCT'95), Lecture Notes in Computer Science, vol. 965, pp.191-200, Springer-Verlag, 1995.
•   H. N. Djidjev, S. M. Venkatesan, Planarization of graphs embedded on surfaces, in Proc. 21st Workshop on Graph-Theoretic Concepts in Computer Science (WG '95), Lecture Notes in Computer Science, vol. 1017, pp. 62-72, Springer-Verlag, 1995.
•   H. Djidjev, G. Pantziou, and C. Zaroliagis, On-line and dynamic algorithms for shortest path problems, in Proc. 12th Symposium on Theoretical Aspects of Computer Science (STACS'95), LNCS 900, pp.193-204, Springer-Verlag, 1995.
•   H. N. Djidjev, A. Lingas, On computing Voronoi diagrams for sorted point sets, International Journal of Computational Geometry, vol. 5 (1995), pp. 327-337.
•   H. N. Djidjev, On drawing a graph convexly in the plane, Graph Drawing '94, DIMACS International Workshop, in Lecture Notes in Computer Science, vol. 894, Springer-Verlag, 1995, pp. 76-83.
•   H. N. Djidjev, K. Diks, O. Sykora, I. Vrto, Edge separators for planar graphs and their applications, Journal of Algorithms, vol. 14 (1993), pp. 258-279.
•   P. Vassilevsky, H. N. Djidjev, Incomplete block preconditioners for solving elliptic differential equations on systolic processors, International Journal of Computer Mathematics, vol. 44 (1992), 341.
•   H. N. Djidjev, A. Lingas, and J.-R. Sack, An O(n log n) algorithm for computing the link center of a simple polygon, Discrete and Computational Geometry, vol. 8 (1992), pp. 131-152.
•   H.N. Djidjev, J. Reif, An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs, Proc. Annual ACM Symposium on Theory of Computing (STOC) (1991), pp.337-347.
•   H. Djidjev, A. Lingas, On computing the Voronoi diagram for restricted planar figures, WADS'91, in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo (1991), pp. 54-64.
• H. Djidjev, O. Garido, C. Levcopoulos, and A. Lingas, On the maximum q-dependent set problem, International Conference for Young Computer Scientists ICYCS'91, pp. 271-274.
•   H.N. Djidjev, G.E. Pantziou, C.D. Zaroliagis, Computing shortest paths and distances in planar graphs, ICALP'91, in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo (1991), v.510, 327-338.
•   L. Aleksandrov, H. N. Djidjev, Improved upper and lower bounds on separation of toroidal graphs, Proc. Optimal algorithms'89, in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo (1989), vol.401, 126-138.
•   H. Djidjev, A. Lingas, and J.-R. Sack, An O(n log n) algorithm for computing a link center in a simple polygon, Proc. STACS '89, in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo (1989), vol. 349, 96-107.
•   H. N. Djidjev, Design and analysis of systolic implementations, J. of New Generation Computing Systems, vol. 1 (1988), 1, 7-20.
•   H. N. Djidjev, Linear algorithms for graph separation problems, SWAT'88, Lecture Notes in Computer Science, vol. 318, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 216-221 (1988).
• K. Diks, H. N. Djidjev, O. Sykora, I. Vrto, Edge separators for planar graphs and their applications, MFCS'88, Lecture Notes in Computer Science, vol. 324, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 280-290 (1988).
•   L. Aleksandrov, H. N. Djidjev, Solving symmetric positive definite systems of linear equations on a systolic processor, Proc. IFIP Working Conference on Parallel Processing, in Parallel Processing, M. Cosnard, M.H.Barton and M. Vaneschi (Eds.), Elsevier Science Publishers (North Holland) (1988).

Books and Book Chapters

• A. Maheshwari, J.R. Sack, and H. Djidjev, Link Distance Problems, Chapter in Handbook on Computational Geometry, Elsevier, 2000, pp. 519-558.
•   V. Aleksandrov, R. Andonov, H. N. Djidjev, V. Josifov, and C.Ostromski, Mathematical Aspects of VLSI Design, Sofia, 1989 (in Bulgarian).

Invited talks

Princeton University, Carnegie-Mellon University, Massachusetts Institute of Technology (MIT), UT Austin, UC Berkeley, Palo Alto Research Center (PARC), University of Washington, University of Lund, Max-Planck Institute (MPII), King's College London, and others

Personal

• US citizen