On Greedy Matching Ordering and Matchable Graphs * (Extended Abstract) Greedy (2009)
Abstract. In this note a greedy algorithm is considered that computes a matching for a graph with a given ordering of its vertices, and those graphs are studied for which a vertex ordering exists...
Succinct Summarization of Transactional Databases: An Overlapped Hyperrectangle Scheme (2009)
Yang Xiang, Ruoming Jin, David Fuhry, Feodor F. Dragan
Transactional data are ubiquitous. Several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. In this work, we propose a new...
A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋆ (2009)
Feodor F. Dragan, Fedorv. Fomin, Petra. Golovach
Abstract. A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. Thesparsest t-spanner problem asks to find,...
Victor Chepoi, Feodor F. Dragan, Yann Vaxès, Bertrand Estellon
δ-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points u, v, w, x, the two larger of the sums d(u, v) +d(w, x),d(u, w) + d(v, x),d(u, x) +d(v,...
Collective Additive Tree Spanners of Homogeneously Orderable Graphs [Extended Abstract] (2009)
Feodor F. Dragan, Chenyu Yan, Yang Xiang
Abstract. In this paper we investigate the (collective) tree spanners problem in homogeneously orderable graphs. This class of graphs was introduced by A. Brandstädt et al. to generalize the dually...
Tree Spanners for Bipartite Graphs and Probe Interval Graphs 1 (2008)
Andreas Br, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Tree Spanners for Bipartite Graphs and Probe Interval Graphs 1 (2008)
Andreas Br, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Abstract. In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with...
Distance Approximating Trees: Complexity and Algorithms (2008)
Abstract. Let Δ ≥ 1andδ ≥ 0 be real numbers. A tree T =(V,E ′)is a distance (Δ, δ)–approximating tree of a graph G =(V,E)ifdH(u, v) ≤ ΔdG(u, v)+δ and dG(u, v) ≤ ΔdH(u, v)+δ hold...
Generalized Powers of Graphs and Their Algorithmic Use (2008)
Abstract. Motivated by the frequency assignment problem in heterogeneous multihop radio networks, where different radio stations may have different transmission ranges, we introduce two new types of...
Abstract. In this paper, motivated by applications of ordinary (distance) spanners in communication networks and to address such issues as bandwidth constraints on network links, link failures,...
68 Collective Tree Spanners and Routing in AT-free Related Graphs (2008)
Feodor F. Dragan, Derekg. Corneil
Abstract. In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G =(V,E) admits a system of µ...
Vol. 20, No. 1, pp. 240–260 COLLECTIVE TREE SPANNERS OF GRAPHS ∗ (2008)
Feodor F. Dragan, Chenyu Yan, Irina Lomonosov
Abstract. In this paper we introduce a new notion of collective tree spanners. We say that a graph G =(V,E) admits a system of μ collective additive tree r-spanners if there is a system T (G) of at...
Practical Approximation Algorithms for Separable Packing Linear Programs (2008)
Feodor F. Dragan, Andrew B. Kahn, Ion I. Mandoiu, Sudhakar Muddu, Alexander Zelikovsky, Er Zelikovsky
We describefVkw polynomial time approximation schemes fm generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Bu#er Blocks (GRBB). We extend...
Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach, B Er, G E Nsis
Spanners in sparse graphs
P.A.: Spanners in sparse graphs (2008)
Feodor F. Dragan, Fedorv. Fomin, Petra. Golovach
Abstract. A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. IfS is required to be a tree then S is called...
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract---To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Feodor F. Dragan, Andrew B. Kahng, Ion I. M, Sudhakar Muddu, Alexander Zelikovsky
Abstract. We describe fully polynomial time approximation schemes for generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Buffer Blocks (GRBB). We extend...
Abstract. Clique-width of graphs is a major new concept with respect to eciency of graph algorithms; it is known that every algorithmic problem expressible in a certain kind of Monadic Second Order...
SIAM J. DISCRETE MATH. c (2007)
Feodor F. Dragan, Falk Nicolai, Brandst Adt
Abstract. It is well known that chordal graphs can be characterized via m-convexity. In this paper we introduce the notion of m 3-convexity (a relaxation of m-convexity) which is closely related to...
Andreas Brandstadt, Feodor F. Dragan, Hoang-oanh Le, Van Bang Le, Ryuhei Uehara
Abstract. A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks...
Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2007)
Feodor F. Dragan, Andrew B. Kahng, Ion I. Măndoiu, Sudhakar Muddu, Alexander Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and per-formance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Abstract. In this paper we show that a very simple and efficient approach can be used to solve the all pairs almost shortest path problem on the class of weakly chordal graphs and its different...
applications in cellular networks (2006)
Victor Chepoi, Feodor F. Dragan, Yann Vaxès, V. Chepoi, F. F. Dragan, Y. Vaxès
Addressing, distances and routing in triangular systems with
Collective tree 1-spanners for interval graphs (2005)
Derek G. Corneil, Feodor F. Dragan
Abstract. In this paper we study the existence of a small set T of spanning trees that collectively “1-span ” an interval graph G. Inparticular, for any pair of vertices u, v we require a tree T...
Distance-based location update and routing in irregular cellular networks (2005)
Victor Chepoi, Feodor F. Dragan, Yann Vaxès
In this paper, we consider a class of cellular networks, called irregular cellular networks, which may have a nonuniform distribution of base stations and a non-uniform cell size. The communication...
Collective Tree Spanners of Graphs (2004)
Feodor F. Dragan, Chenyu Yan, Irina Lomonosov
In this paper we introduce a new notion of collective tree spanners. We say that a graph G =(V,E) admits a system of collective additive tree r-spanners if there is a system spanning trees of G such...
On Compact and Efficient Routing in Certain Graph Classes (2004)
Feodor F. Dragan, Irina Lomonosov
Abstract. In this paper we refine the notion of tree-decomposition by introducing acyclic (R, D)-clustering, where clusters are subsets of vertices of a graph and R and D are the maximum radius and...
Collective tree spanners and routing in AT-free related graphs (extended abstract (2004)
Feodor F. Dragan, Chenyu Yan, Derek G. Corneil
In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph G = (V, E) admits a system of µ collective...
On the power of bfs to determine a graph’s diameter (2003)
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler
Recently, considerable effort has been spent on showing that Lexicographic Breadth First Search (LBFS) can be used to determine a tight bound on the diameter of graphs from various restricted...
On Linear and Circular Structure of (claw, Net)-Free Graphs (2003)
Andreas Brandstädt, Andreas Br, Stadt A, Feodor F. Dragan
We prove that every (clyn net)-free graph contains an induceddoubl dominatingcycl or a dominating pair. Moreover, using LexBFS we present alS[SE timealen##ES which, for a given (clen net)-free graph,...
Additive spanners for k-chordal graphs (2003)
Victor D. Chepoi, Feodor F. Dragan, Chenyu Yan
Abstract. In this paper we show that every chordal graph with n vertices and m edges admits an additive 4-spanner with at most 2n−2 edges and an additive 3-spanner with at most O(n · log n) edges....
families: a unified approach ✩ (2002)
www.elsevier.com/locate/jalgor Estimating all pairs shortest paths in restricted graph
Provably good global buffering by multiterminal multicommodity flow approximation (2001)
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Ion M, Alexander Zelikovsky, Sudhakar Muddu, ...
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
In this paper those graphs are studied for which a so-called strong ordering of the vertex set exists. This class of graphs, called strongly orderable graphs, generalizes the strongly chordal graphs...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Sudhakar Muddu, Alexander Zelikovsky, Er Zelikovsky
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
On Stable Cutsets in Graphs (2000)
Andreas Brandstädt, Andreas Br, Stadt A, Feodor F. Dragan, Van Bang Le, Thomas Szymczak
We answer a question of Corneil and Fonlupt by showing that deciding whether a graph has a stable cutset is NP-complete even for restricted graph classes. Some efficiently solvable cases will be...
Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs (1999)
Andreas Brandst Adt, Feodor F. Dragan, K Ohler
Abstract. We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a...
Almost diameter of a house-hole-free graph in linear time via LexBFS (1999)
We show that the vertex visited last by a LexBFS has eccentricity at least diam(G) - 2 for house-hole-free graphs, at least diam(G) - 1 for house-hole-domino-free graphs, and equal to diam(G) for...
Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs (1999)
Andreas Brandst Ädt, Feodor F. Dragan, K Öhler
Abstract. We prove that claw-free graphs, containingan induced dominatingpath, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair...
Convexity and HHD-free graphs (1999)
Feodor F. Dragan, Falk Nicolai, Andreas Brandstädt
It is well known that chordal graphs can be characterized via m-convexity. In this paper we introduce the notion of m 3-convexity (a relaxation of m-convexity) which is closely related to...
Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs (1997)
Andreas Brandstädt, Andreas Brandst Adt, Feodor F. Dragan, Victor D. Chepoi, F. Dragan
. Let C be a family of cliques of a graph G =(V,E). Suppose that each clique C of C is associated with an integer r(C), where r(C) # 0. A vertex vr-dominates a clique C of G if d(v, x) # r(C) for all...
Clique r-domination and clique r-packing problems on dually chordal graphs (1997)
Andreas Brandstädt, Victor D. Chepoi, Feodor F. Dragan
Let C be a family of cliques of a graph G =(V,E). Suppose that each clique C of C is associated with an integer r(C), where r(C) ≥ 0. A vertex vr-dominates a clique C of G if d(v, x) ≤ r(C) for...
LexBFS-orderings and powers of graphs (1997)
Feodor F. Dragan, Falk Nicolai, Andreas Br
Abstract. For an undirected graph G the k-th power G ~ of G is the graph with the same vertex set as G where two vertices are adjacent iff their distance is at most k in G. In this paper we consider...
r-domination problems on homogeneously orderable graphs (1995)
Feodor F. Dragan, Falk Nicolai
Abstract: In this paper, we consider r-dominating cliques in homogeneously orderable graphs ( a common generalization of dually chordal and distance-hereditary graphs) and their relation to strict...
Abstract: A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We...
Dominating cliques in distance-hereditary graphs (1994)
Abstract. A graph is distance-hereditary if and only if each cycle on five or more vertices has at least two crossing chords. We present linear time algorithms for the minimum r-dominating clique and...