Feodor F. Dragan's Selected On-line Publications

(see my CV for on-line versions of more recent papers)

 

  • Effective Monitor Placement in Internet Networks
    Y. Breitbart , F.F. Dragan, H. Gobjuka
    Journal of Networks 4 (2009), 657-666. pdf
  • Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
    C. Yan, Y. Xiang and F.F. Dragan
    The Algorithms And Data Structures Symposium (WADS 2009), Banff Conference Centre, Banff, Alberta, Canada, 21-23 August 2009, Springer, Lecture Notes in Computer Science, 5664, pp. 566-577. ppt     pdf
  • How to use spanning trees to navigate in graphs
    F.F. Dragan and Y. Xiang
    34th International Symposium on Mathematical Foundations of Computer Science (MFCS 2009), August 24 - 28, 2009, Novy Smokovec, High Tatras, Slovak Republic, Springer, Lecture Notes in Computer Science 5734, pp. 282-294.     ppt pdf
  • Collective Tree Spanners for Unit Disk Graphs with Applications
    F.F. Dragan, Y. Xiang and C. Yan
    Electronic Notes in Discrete Mathematics 32 (2009) 117-124.     ppt pdf
  • Navigating in a graph by aid of its spanning tree
    F.F. Dragan and M. Matamala
    19th International Symposium on Algorithms and Computation (ISAAC 2008), Surfers Paradise, Gold Coast, Australia, December 15-17, 2008, Springer, Lecture Notes in Computer Science 5369, pp. 789-800, 2008. ppt pdf
  • Overlapping Matrix Pattern Visualization: a Hypergraph Approach
    R. Jin, Y. Xiang, D. Fuhry, F.F. Dragan
    IEEE International Conference on Data Mining (IEEE-ICDM 2008), Pisa, Italy, December 15-19, 2008, pp. 313-322. ppt     pdf
  • A PTAS for the sparsest spanners problem on apex-minor-free graphs
    F.F. Dragan, F. Fomin and P. Golovach
    33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland, August 27-31, 2008, Springer, Lecture Notes in Computer Science 5162, pp. 290-298. ppt pdf
  • Succinct Summarization of  Transactional Databases: An Overlapped Hyperrectangle Scheme
    Y. Xiang, R. Jin, D. Fuhry, F.F. Dragan
    14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2008), Las Vegas, USA, 24-27 August, 2008, pp. 758-766. ppt pdf
  • Spanners in sparse graphs
    F.F. Dragan, F. Fomin and P. Golovach
    35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, July 6-13, 2008, Springer, Lecture Notes in Computer Science 5125 (Part I), pp. 597-608. ppt pdf
  • Additive Spanners for Circle Graphs and Polygonal Graphs
    F.F. Dragan, D.G. Corneil, E. Koehler and Y. Xiang
    34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), Durham University, U.K., June 30- July 2, 2008, Springer, Lecture Notes in Computer Science 5344, pp. 110-121, 2008. pdf
  • Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
    V.D. Chepoi, F.F. Dragan, B. Estellon, M. Habib and Y. Vaxes
    Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), June 9-11, 2008, College Park, Maryland, USA, pp. 59-68. ppt pdf
  • Notes on diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs
    V.D. Chepoi, F.F. Dragan, B. Estellon, M. Habib and Y. Vaxes
    International Conference on Topological and Geometric Graph Theory (TGGT 2008), Electronic Notes in Discrete Mathematics 31 (2008), 231-234. pdf
  • Collective Additive Tree Spanners of Homogeneously Orderable Graphs
    F.F. Dragan, C. Yan, Y. Xiang
    8th Latin American Symposium on Theoretical Informatics (LATIN 2008), Buzios, Brazil, April 7-11, 2008, Springer, Lecture Notes in Computer Science 4957, pp.555-567. ppt pdf
  • Spanners for bounded tree-length graphs   
    Y. Dourisboure, Dragan F.F., C. Gavoille, and C. Yan
    Theoretical. Computer Science 383 (2007),   34-44. pdf
  • On compact and efficient routing in certain graph classes
    Dragan F.F. and I. Lomonosov
    Discrete Applied Mathematics 155 (2007), 1458-1470. pdf
  • Tree spanners for bipartite graphs and probe interval graphs
    A. Brandstaedt, Dragan F.F., H.-O. Le, V.B. Le and R. Uehara
    Algorithmica 47 (2007), 27-51. pdf
  • Collective Tree Spanners and Routing in AT-free Related Graphs
    F.F. Dragan, C. Yan and D.G. Corneil
    Journal of Graph Algorithms and Applications, Vol. 10, no. 2, 2006, 97-122. pdf
  • Generalized Powers of Graphs and Their Algorithmic Use
    A. Brandstaedt, F.F. Dragan, Y. Xiang and C. Yan
    Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT' 06), Riga, Latvia, July 6-8, 2006,  Springer, Lecture Notes in Computer Science 4059, pp. 423-434. ppt pdf
  • Collective tree spanners of graphs
    F.F. Dragan, C. Yan and I. Lomonosov
    SIAM J. Discrete Math. 20 (2006),  241-260. pdf
  • Distance Approximating Trees: Complexity and Algorithms
    F.F. Dragan and C. Yan
    In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC' 2006), Rome, Italy, May 29-31, 2006, Springer, Lecture Notes in Computer Science 3998, pp. 260-271. ppt  pdf
  • Network Flow Spanners
    F.F. Dragan and C. Yan
    In Proceedings of the 7th Latin American Symposium ''LATIN 2006: Theoretical Informatics'', Valdivia, Chile, March 20-24, Springer, Lecture Notes in Computer Science 3887, pp. 410-422. ppt poster  pdf
  • Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-width, or Clique-width 
    F.F. Dragan and C. Yan
    In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), December 19-21, 2005, Hainan, China, Springer, Lecture Notes in Computer Science 3827, pp. 583-592. ppt  pdf
  • Addressing, distances and routing in triangular systems with applications in cellular networks
    V.D. Chepoi, F.F. Dragan, Y. Vaxes
    Wireless Networks 12 (2006), 671-679. The special issue "Best papers of the 4th Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN 2004)". pdf
  • Distance and routing labeling schemes for non-positively curved plane graphs
    V.D. Chepoi, F.F. Dragan, Y. Vaxes
    Journal of Algorithms 61 (2006), 60-88.   Journal version (pdf)  Full version (pdf)
  • Collective tree 1-spanners for interval graphs
     D.G. Corneil, F.F. Dragan, E. Koehler and C. Yan
    In Proceedings of 31st International Workshop "Graph-Theoretic Concepts in Computer Science" (WG '05), June 23-25, 2005, Metz, France, Springer, Lecture Notes in Computer Science 3787, pp. 151-162.  pdf
  • Distance-Based Location Update and Routing in Irregular Cellular Networks
     V.D. Chepoi, F.F. Dragan, Y. Vaxes
    In Proceedings of Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Networks (SNPD/SAWN'05), May 23-25, 2005, Towson University, Maryland, USA, IEEE Computer Society, 2005, pp. 380-387. ppt  pdf
  • Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach
    Dragan F.F.
    Journal of Algorithms 57 (2005), 1-21. (one of the TOP25 Hottest Articles within the Journal of Algorithms for   Jan-Mar 2005, Jul-Sep 2005, Oct-Dec 2005, Jan-Mar 2006, Apr-Jun 2006)  pdf
  • New Graph Classes of Bounded Clique Width
    A. Brandstaedt, Dragan F.F., Hoang-Oanh Le, Raffaele Mosca
    Theory of Computing Systems 38 (2005), 623-645. ps
  • Additive Sparse Spanners for Graphs with Bounded Length of Largest Induced Cycle
    V.D. Chepoi, Dragan F.F., and Chenyu Yan
    Theoretical Computer Science 347 (2005), 54-75.  pdf
  • On Compact and Efficient Routing in Certain Graph Classes
    F.F. Dragan, I. Lomonosov
    In Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), December 20 - 22, 2004, HKUST, Hong Kong, Springer, Lecture Notes in Computer Science 3341, pp. 402-414.  pdf
  • Effective Network Monitoring
    Y. Breitbart, F.F. Dragan, H. Gobjuka
    13th International Conference on Computer Communications and Networks (ICCCN 2004), October 11-13, 2004 Chicago, IL USA, pp. 394-399.  pdf
  • Collective Tree Spanners and Routing in AT-free Related Graphs
    F.F. Dragan, C. Yan and D.G. Corneil
    In Proceedings of 30th International Workshop "Graph-Theoretic Concepts in Computer Science" (WG '04), June 2004, Hoelterhoff House at Bad Honnef, close to Bonn, Germany, Springer, Lecture Notes in Computer Science 3353, pp. 68-80.  ppt   pdf
  • Collective tree spanners of graphs
    F.F. Dragan, C. Yan and I. Lomonosov
    Proc. of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04), 8-10 July, 2004, Humlebaek, Denmark, Springer, Lecture Notes in Computer Science 3111, pp. 64-76.  ppt   pdf
  • Addressing, distances and routing in triangular systems with applications in cellular and sensor networks
    V.D. Chepoi, F.F. Dragan, Y. Vaxes
    Proc. of the 18th International Parallel & Distributed Processing Symposium, April 26 - 30, Santa Fe, New Mexico (4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, WMAN'04) (on CD), 2004.  ppt   pdf
  • Tree Spanners on Chordal Graphs: Complexity and Algorithms
    A. Brandstaedt, Dragan F.F., H.-O. Le, and V.B. Le
    Theoretical Computer Science  310 (2004), 329-354. ppt    pdf
  • Tree spanners for bipartite graphs and probe interval graphs
    A. Brandstaedt, Dragan F.F., H.-O. Le, V.B. Le and R. Uehara
    In Proceedings of 29th International Workshop "Graph-Theoretic Concepts in Computer Science" (WG '03), June 2003, Elspeet, the Netherlands, Springer, Lecture Notes in Computer Science 2880, pp. 106-118, 2003. ppt  pdf
  • Additive Spanners for k-Chordal Graphs
    V. Chepoi, Dragan F.F., and Chenyu Yan
    In Proceedings of 5th Conference on Algorithms and Complexity (CIAC 2003), May 28-30, 2003, Rome, Italy, Springer, Lecture Notes in Computer Science 2653, pp.96-107. ppt   pdf
  • On the power of BFS to determine a graph's diameter
    Corneil D.G., Dragan F.F. and E. Koehler
    Networks 42 (2003), 209-222.  ppt  pdf
  • Finding a central vertex in HHD-free graphs
    Chepoi V.D. and Dragan F.F.
    Discrete Appl. Math. 131 (2003), 93-111.  pdf
    Editors Choice 2003, a representative collection of excellent papers published in Discrete Appl. Math. in 2003. 
  • On linear and circular structure of a (claw,net)-free graph
    A. Brandstaedt and Dragan F.F.
    Discrete Appl. Math. 129 (2003), 285-303.  pdf
  • Provably good global buffering by generalized multiterminal multicommodity flow approximation
    Dragan F.F., A. B. Kahng, S. Muddu, I. Mandoiu and A. Zelikovsky
    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21 (2002), 263-274.  pdf
  • Center and diameter problems in plane triangulations and quadrangulations
    Chepoi V.D., Dragan F.F., Y. Vaxes
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), San Francisco, CA, January 2002, pp. 346-355. ppt  ps
  • Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach (extended abstract)
    Dragan F.F.
    Proc. 27th International Workshop ''Graph-Theoretic Concepts in Computer Science''(WG'01), June 2001, Springer, Lecture Notes in Computer Science 2204, pp. 103-116. ppt   pdf
  • Practical Approximation Algorithms for Separable Packing Linear Programs
    Dragan F.F., A. B. Kahng, S. Muddu, I. Mandoiu and A. Zelikovsky
    Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS'01), August, 2001, Springer, Lecture Notes in Computer Science 2125, pages 325-337.  pdf
  • Provably good global buffering by multiterminal multicommodity flow approximation
    Dragan F.F., A. B. Kahng, S. Muddu, I. Mandoiu and A. Zelikovsky
    Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC'01), January/February, 2001, pages 139-144. ppt   pdf
  • Diameter Determination on Restricted Graph Families
    Corneil D.G., Dragan F.F., Habib M. and Paul C.
    Discrete Appl. Math. 113 (2001), 143-166. pdf
  • Provably Good Global Buffering Using an Available Buffer Block Plan
    Dragan F.F., A. B. Kahng, S. Muddu, I. Mandoiu and A. Zelikovsky
    Proc. of IEEE/ACM Intl. Conference on Computer-Aided Design (ICCAD'00), November, 2000, pages 104-109.  ppt   pdf
  • Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs
    A. Brandstaedt, Dragan F.F. and E. Koehler
    SIAM J. on Computing 30 (2000), 1662-1677. pdf   ps
  • On stable cutsets in graphs
    A. Brandstaedt, Dragan F.F., V.B. Le , and Th. Szymczak
    Discrete Appl. Math.  105 (2000), 39-50. pdf
  • A note on distance approximating trees in graphs
    Chepoi V.D. and Dragan F.F.
    European Journal of Combinatorics  21 (2000), 761-766. pdf
  • Strongly orderable graphs:
    A common generalization of strongly chordal and chordal bipartite graphs
    Dragan F.F.
    Discrete Appl. Math. 99 (2000), 427-442. pdf
  • LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
    Dragan F.F. and Nicolai F.
    Discrete Appl. Math. 98 (2000), 191-207. pdf
  • Almost diameter of a House-Hole-free graph in linear time via LexBFS
    Dragan F.F.
    Discrete Appl. Math. 95 (1999), 223-239. pdf
  • Distance approximating trees for chordal and dually chordal graphs
    A. Brandstaedt, Chepoi V.D. and Dragan F.F.
    Journal of Algorithms. 30 (1999), 166-184. pdf
  • Convexity and HHD-free graphs
    Dragan F.F., Nicolai F. and A. Brandstaedt
    SIAM J. Discrete Math. 12 (1999), 119-135. pdf  ps
  • A linear-time algorithm for connected r-domination and Steiner tree on distance-hereditary graphs
    A. Brandstaedt and Dragan F.F.
    Networks  31 (1998), 177-182. pdf
  • Dually chordal graphs
    A. Brandstaedt, Dragan F.F., Chepoi V.D. and Voloshin V.I.
    SIAM J. Discrete Math.  11 (1998), 437-455. pdf  ps
  • The algorithmic use of hypertree structure and maximum neighbourhood orderings
    A. Brandstaedt, Chepoi V.D. and Dragan F.F.
    Discrete Appl. Math.  82 (1998), 43-77. pdf
  • LexBFS-orderings and powers of chordal graphs
    A. Brandstaedt, Dragan F.F. and Nicolai F.
    Discrete Math.,  171 (1997), 27-42. pdf
  • r -Domination Problems on Homogeneously orderable graphs
    Dragan F.F. and Nicolai F.
    Networks,  30 (1997), 121-131. pdf
  • Homogeneously orderable graphs
    A. Brandstaedt, Dragan F.F. and Nicolai F.
    Theoretical Computer Science, 172 (1997), 209-232. pdf
  • Clique r -domination and clique r -packing problems on dually chordal graphs
    A. Brandstaedt, Chepoi V.D. and Dragan F.F.
    SIAM J. Discrete Math., 10(1997), 109-127. pdf  ps
  • On Greedy Matching Ordering and Greedy Matchable Graphs (Extended Abstract)
    Dragan F.F.
    WG 1997: 184-198. pdf
  • Condorcet and median points of simple rectilinear polygons
    Chepoi V.D. and Dragan F.F.
    Location Science, 4 (1996),  21-35. pdf
  • Perfect elimination orderings of chordal powers of graphs
    A. Brandstaedt, Chepoi V.D. and Dragan F.F.
    Discrete Math., 158 (1996),  273-278. pdf
  • r -Dominating cliques in graphs with hypertree structure
    Dragan F.F. and A. Brandstaedt
    Discrete Math., 162 (1996),  93-108. pdf
  • Incidence graphs of biacyclic hypergraphs
    Dragan F.F. and Voloshin V.I.
    Discrete Appl. Math.,  68 (1996),  259-266. pdf
  • LexBFS-orderings and powers of graphs
    Dragan F.F., Nicolai F. and A. Brandstaedt
    WG 1996: 166-180. pdf
  • Dominating Cliques in Distance-Hereditary Graphs
    Dragan F.F.
    SWAT 1994: 370-381. pdf
  • A Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph
    Chepoi V.D. and Dragan F.F.
    ESA 1994: 159-170. pdf
  • On link diameter of a simple rectilinear polygon
    Chepoi V.D. and Dragan F.F.
    Computer Science J. of Moldova (Kishinev), 1993, Vol.1, N 3, 62-74. pdf
  • Domination in quadrangle-free Helly graphs
    Dragan F.F.
    Cybernetics and Systems Analysis, 29, No.6, (1993), 822-829 (English. Russian original);
    translation from Kibernetika i Sistemnyi Analiz, 1993, No.6, 47-57. pdf
  • HT-graphs: centers, connected r-domination and Steiner trees
    Dragan F.F.
    Computer Science J. of Moldova (Kishinev), 1993, Vol.1, N 2, 64-83. pdf

 

Back to Feodor F. Dragan's Home Page
Last updated: September 2016