In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomialtime algorithms. We specifically target radius (minimum eccentricity), diameter (maximum eccentricity), and all-eccentricity computations for which quadratic-time lower bounds are known under plausible conjectures. In each case, we introduce a notion of certificate as a specific set of nodes from which appropriate bounds on all eccentricities can be derived in subquadratic time when this set has sublinear size. The existence of small certificates is a barrier against SETH-based lower bounds for these problems. We indeed prove that for graph classes with small certificates, there exist randomized subquadratic-time algorithms for computing the radius, the diameter, and all eccentricities respectively.

Abstract We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called $$\alpha _i$$ α i -metric ( $$i\in {\mathcal {N}}$$ i ∈ N ) if it satisfies the following $$\alpha _i$$ α i -metric property for every vertices u, w, v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then $$d(u,x)\ge d(u,v) + d(v,x)-i$$ d ( u , x ) ≥ d ( u , v ) + d ( v , x ) - i . Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a “near-shortest” path with defect at most i. It is known that $$\alpha _0$$ α 0 -metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are $$\alpha _i$$ α i -metric for $$i=1$$ i = 1 and $$i=2$$ i = 2 , respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an $$\alpha _i$$ α i -metric graph can be computed in total linear time. Our strongest results are obtained for $$\alpha _1$$ α 1 -metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called $$(\alpha _1,\varDelta )$$ ( α 1 , Δ ) -metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in Dragan (Inf Probl Lett 154:105873, 2020), 2020). Our algorithms follow from new results on centers and metric intervals of $$\alpha _i$$ α i -metric graphs. In particular, we prove that the diameter of the center is at most $$3i+2$$ 3 i + 2 (at most 3, if $$i=1$$ i = 1 ). The latter partly answers a question raised in Yushmanov and Chepoi (Math Probl Cybernet 3:217–232, 1991).

Abstract We present new algorithmic results for the class of Helly graphs, that is, for the discrete analogues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. It is known that every graph isometrically embeds into a Helly graph that makes of the latter an important class of graphs in metric graph theory. We study diameter and radius computations within the Helly graphs, and related graph classes. This is in part motivated by a conjecture on the fine‐grained complexity of these two distance problems within the graph classes of bounded fractional Helly number—that contain as particular cases the proper minor‐closed graph classes and the bounded clique‐width graphs. Note that under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, we first present algorithms which given an n‐vertex m‐edge Helly graph G as input, compute with high probability (w.h.p.) its radius and its diameter in time (i.e., subquadratic in n + m). Our algorithms are based on the Helly property and on the unimodality of the eccentricity function in Helly graphs: every vertex of locally minimum eccentricity is a central vertex. Then, we improve our results for the C4‐free Helly graphs, that are exactly the Helly graphs whose balls are convex. For this subclass, we present linear‐time algorithms for computing the eccentricity of all vertices. Doing so, we generalize previous results on strongly chordal graphs to a much larger subclass, that includes, among others, all the bridged Helly graphs and the hereditary Helly graphs. Lastly, we derive approximate versions of our results for the class of chordal graphs: with the latter satisfying an almost‐Helly‐type property, and a stronger (induced‐path) convexity property than the C4‐free Helly graphs. For the chordal graphs, we can compute in quasi linear time the eccentricity of all vertices with an additive one‐sided error of at most one, which is best possible under the strong exponential‐time hypothesis. This answers an open question of Dragan. In fact, we obtain this last result as a byproduct from a more general reduction: from diameter computation on chordal graphs to the Disjoint Sets problem. Roughly, it implies that the split graphs are the only hard instances for diameter computation on chordal graphs. We also get from our reduction that on any subclass of chordal graphs with constant VC‐dimension (and so, for undirected path graphs), the diameter can be computed in truly subquadratic time.

To help compute shortest path distances over large graphs efficiently, 2-hop labeling has emerged as a major tool, with Pruned Landmark Labeling (PPL) as a popular algorithm. This paper demonstrates the first scalable parallel implementation of the PPL algorithm that produces the same results as the sequential algorithm. Based on theoretical analysis, we show how computations on each vertex can be performed in parallel while maintaining correctness, resulting in the Vertex-Centrix PLL (VC-PLL) algorithm. We also show a formulation of this algorithm based on linear algebra and argue why the use of a library based on linear algebra operations will not produce an efficient implementation. Next, we introduce a batched VC-PLL (BVC-PLL) algorithm to reduce the computational inefficiency in VC-PLL. We have carried out a parallel implementation of this method for modern clusters, combining shared memory and distributed memory parallelism, that can efficiently execute on graphs with more than a billion edges. We also demonstrate how BVC-PLL algorithm can be extended to handle directed graphs and weighted graphs and how the version for weighted graphs can benefit from SIMD parallelization.

In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of vertices of a graph with δ-thin geodesic triangles (in particular, of a δ-hyperbolic graph) G there exists a vertex m of G such that the ball B(m, 4δ) of radius 4δ centered at m intercepts at least one half of the total flow between all pairs of vertices of X, where the flow between two vertices x,y ∊ X is carried by geodesic (or quasi-geodesic) (x, y)-paths. Moreover, we prove a primal- dual result showing that, for any commodity graph R on X and any r ≥ 8δ, the size στ(R) of the least r-multi-core (i.e., the number of balls of radius r) intercepting all pairs of R is upper bounded by the maximum number of pairwise (2r – 5δ)- apart pairs of R and that an r-multi-core of size σr–5δ (R) can be computed in polynomial time for every finite set X. Our result about total r-multi-cores is based on a Helly-type theorem for quasiconvex sets in δ-hyperbolic graphs (this is our second main result). Namely, we show that for any finite collection Q of pairwise intersecting ∊-quasiconvex sets of a δ-hyperbolic graph G there exists a single ball B(c, 2∊ + 5δ) intersecting all sets of Q. More generally, we prove that if Q is a collection of 2r-close (i.e., any two sets of Q are at distance ≤ 2r) ε-quasiconvex sets of a δ-hyperbolic graph G, then there exists a ball B(c,r*) of radius r* := max{2e + 5δ, r + e + 3δ} intersecting all sets of Q. These kind of Helly-type results are also useful in geometric group theory. Using the Helly theorem for quasiconvex sets and a primal-dual approach, we show algorithmically that the minimum number of balls of radius 2∊ + 5δ intersecting all sets of a family Q of ∊-quasiconvex sets does not exceed the packing number of Q (maximum number of pairwise disjoint sets of Q). We extend the covering and packing result to set-families KQ in which each set is a union of at most κ ε-quasiconvex sets of a δ-hyperbolic graph G. Namely, we show that if r ≥ ∊ + 2δ and nr (κ Q) is the maximum number of mutually 2r-apart members of κ Q, then the minimum number of balls of radius r + 2∊ + 6δ intersecting all members of KQ is at most 2K2nr(KQ) and such a hitting set and a packing can be constructed in polynomial time for every finite KQ (this is our third main result). For set- families consisting of unions of κ balls in δ-hyperbolic graphs a similar result was obtained by Chepoi and Estellon (2007). In case of δ = 0 (trees) and ∊ = r = 0, (subtrees of a tree) we recover the result of Alon (2002) about the transversal and packing numbers of a set-family in which each set is a union of at most κ subtrees of a tree.

Based on solid theoretical foundations, we present strong evidence that a number of real‐world networks, taken from different domains (such as Internet measurements, biological data, web graphs, and social and collaboration networks) exhibit tree‐like structures from a metric point of view. We investigate a few graph parameters, namely, the tree‐distortion and the tree‐stretch, the tree‐length and the tree‐breadth, Gromov's hyperbolicity, the cluster‐diameter and the cluster‐radius in a layering partition of a graph; such parameters capture and quantify this phenomenon of being metrically close to a tree. By bringing all those parameters together, we provide efficient means for detecting such metric tree‐like structures in large‐scale networks. We also show how such structures can be used. For example, they are helpful in efficient and compact encoding of approximate distance and almost shortest path information and in quick and accurate estimation of diameters and radii of those networks. Estimating the diameter and estimating the radius of a graph (or distances between arbitrary vertices) are fundamental primitives in many network and graph mining algorithms. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 49–68 2016

Let $G=(V,E)$ be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, $z=x$), unless $z=y$, go to a neighbor of z in G that is closest to y in T (breaking ties arbitrarily). In this strategy, each vertex has full knowledge of its neighborhood in G and can use the distances in T to navigate in G. Thus, additionally to standard local information (the neighborhood $N_G(v)$), the only global information that is available to each vertex v is the topology of the spanning tree T (in fact, v can know only a very small piece of information about T and still be able to infer from it the necessary tree-distances). For each source vertex x and target vertex y, this way, a path, called a greedy routing path, is produced. Denote by $g_{G,T}(x,y)$ the length of a longest greedy routing path that can be produced for x and y using this strategy and T. We say that a spanning tree T of a graph G is an additive r-carcass for G if $g_{G,T}(x,y)\leq d_G(x,y)+r$ for each ordered pair $x,y\in V$. In this paper, we investigate the problem, given a graph family $\mathcal{F}$, of whether a small integer r exists such that any graph $G\in\mathcal{F}$ admits an additive r-carcass. We show that rectilinear $p\times q$ grids, hypercubes, distance-hereditary graphs, dually chordal graphs (and, therefore, strongly chordal graphs and interval graphs) all admit additive 0-carcasses. Furthermore, every chordal graph G admits an additive $(\omega+1)$-carcass (where $\omega$ is the size of a maximum clique of G), each 3-sun-free chordal graph admits an additive 2-carcass, and each chordal bipartite graph admits an additive 4-carcass. In particular, any k-tree admits an additive $(k+2)$-carcass. All those carcasses are easy to construct in sequential as well as in distributed settings.

Abstract In this article, motivated by applications of ordinary (distance) spanners in communication networks and to address such issues as bandwidth constraints on network links, link failures, network survivability, etc., we introduce a new notion of flow spanner, where one seeks a spanning subgraph H = (V, E') of a graph G = (V, E) which provides a “good” approximation of the source‐sink flows in G. We formulate several variants of this problem and investigate their complexities. Special attention is given to the version where H is required to be a tree. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

δ-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,w) differ by at most 2δ. Given a finite set S of points of a δ-hyperbolic space, we present simple and fast methods for approximating the diameter of S with an additive error 2δ and computing an approximate radius and center of a smallest enclosing ball for S with an additive error 3δ. These algorithms run in linear time for classical hyperbolic spaces and for δ-hyperbolic graphs and networks. Furthermore, we show that for δ-hyperbolic graphs G=(V,E) with uniformly bounded degrees of vertices, the exact center of S can be computed in linear time O(|E|). We also provide a simple construction of distance approximating trees of δ-hyperbolic graphs G on n vertices with an additive error O(δlog2 n). This construction has an additive error comparable with that given by Gromov for n-point δ-hyperbolic spaces, but can be implemented in O(|E|) time (instead of O(n2)). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity.

In this work, we study a visual data mining problem: Given a set of discovered overlapping submatrices of interest, how can we order the rows and columns of the data matrix to best display these submatrices and their relationships? We find this problem can be converted to the hypergraph ordering problem, which generalizes the traditional minimal linear arrangement (or graph ordering) problem and then we are able to prove the NP-hardness of this problem. We propose a novel iterative algorithm which utilize the existing graph ordering algorithm to solve the optimal visualization problem. This algorithm can always converge to a local minimum. The detailed experimental evaluation using a set of publicly available transactional datasets demonstrates the effectiveness and efficiency of the proposed algorithm.

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 research problem to succinctly summarize transactional databases. Solving this problem requires linking the high level structure of the database to a potentially huge number of frequent itemsets. We formulate this problem as a set covering problem using overlapped hyperrectangles; we then prove that this problem and its several variations are NP-hard. We develop an approximation algorithm HYPER which can achieve a ln(k) + 1 approximation ratio in polynomial time. We propose a pruning strategy that can significantly speed up the processing of our algorithm. Additionally, we propose an efficient algorithm to further summarize the set of hyperrectangles by allowing false positive conditions. A detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases.

In this paper we introduce a new notion of collective tree spanners. We say that a graph G=(V,E)admits a system of $\mu$ collective additive tree r-spanners if there is a system T(G) of at most $\mu$ spanning trees of G such that for any two vertices x,y of G a spanning tree T\in \cT(G) exists such that d_T(x,y)\leq d_G(x,y)+r. Among other results, we show that any chordal graph, chordal bipartite graph or cocomparability graph admits a system of at most log 2 n collective additive tree 2-spanners. These results are complemented by lower bounds, which say that any system of collective additive tree 1-spanners must have $\Omega(\sqrt{n})$ spanning trees for some chordal graphs and $\Omega(n)$ spanning trees for some chordal bipartite graphs and some cocomparability graphs. Furthermore, we show that any c-chordal graph admits a system of at most log 2 n collective additive tree (2\lfloor c/2\rfloor)-spanners, any circular-arc graph admits a system of two collective additive tree 2-spanners. Towards establishing these results, we present a general property for graphs, called (\al,r)$-decomposition, and show that any $(\al,r)$-decomposable graph G with n vertices admits a system of at most $\log_{1/\al} n$ collective additive tree $2r$-spanners. We discuss also an application of the collective tree spanners to the problem of designing compact and efficient routing schemes in graphs. For any graph on n vertices admitting a system of at most $\mu$ collective additive tree r-spanners, there is a routing scheme of deviation r with addresses and routing tables of size $O(\mu \log^2n/\log \log n)$ bits per vertex. This leads, for example, to a routing scheme of deviation $(2\lfloor c/2\rfloor)$ with addresses and routing tables of size $O(\log^3n/\log \log n)$ bits per vertex on the class of c-chordal graphs.

In this paper, we consider a class of cellular networks, called irregular cellular networks, which may have a non-uniform distribution of base stations and a non-uniform cell size. The communications (between base stations) graph of such a cellular network forms a so-called trigraph, i.e., a plane triangulation with inner vertices of degree at least six. We show that each trigraph with n vertices admits a labeling that assigns O(log/sup 2/ n) bit labels to vertices of the graph such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the graph. Furthermore, we show that there is a labeling, assigning labels of size O(log/sup 2/ n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These two results for trigraphs provide elegant solutions to a few problems in irregular cellular networks. The distance labeling scheme allows efficient implementation of the distance-based tracking protocol, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide compact and efficient routing and connection re-routing protocols. Although these results are primarily developed for cellular networks, they may find applications also in other types of wireless networks that have a fixed backbone infrastructure.

Various network monitoring and performance evaluation schemes generate considerable amount of traffic, which affects network performance. In this paper we describe a method for minimizing network monitoring overhead based on shortest path tree (SPT) protocol. We describe two different variations of the problem: the A-problem and the E-problem, and show that there is a significant difference between them. We prove that finding optimal solutions is NP-hard for both variations, and propose a theoretically best possible heuristic for the A-problem and three different heuristics for the E-problem, one of them being also theoretically best possible. We show that one can compute in polynomial time an O(ln|V|)-approximate solution for each of these problems. Then, we analyze the performance of our heuristics on large graphs generated using Waxman and power-law models as well as on real ISP topology maps. Experiment results show more than 80% improvement when using our heuristics on real topologies over the naive approaches

Summary form only given. Triangular systems are the subgraphs of the regular triangular grid which are formed by a simple circuit of the grid and the region bounded by this circuit. They are used to model cellular networks where nodes are base stations. We propose an addressing scheme for triangular systems by employing their isometric embeddings into the Cartesian product of three trees. This embedding provides a simple representation of any triangular system with only three small integers per vertex, and allows to employ the compact labeling schemes for trees for distance queries and routing. We show that each such system with n vertices admits a labeling that assigns O(log/sup 2/n) bit labels to vertices of the system such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the system. Furthermore, there is a labeling, assigning labels of size O(log n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These results are used in solving some problems in cellular networks. Our addressing and distance labeling schemes allow efficient implementation of distance and movement based tracking protocols in cellular networks, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide elegant and efficient routing and connection rerouting protocols for cellular networks.

Abstract 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 classes. In this paper, we show that, in some cases, the full power of LBFS is not required and that other variations of Breadth First Search (BFS) suffice. The restricted graph classes that are amenable to this approach all have a small constant upper bound on the maximum‐sized cycle that may appear as an induced subgraph. We show that, on graphs that have no induced cycle of size greater thank, BFS finds an estimate of the diameter that is no worse than diam(G) − ⌊k/2⌋. © 2003 Wiley Periodicals, Inc.

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 structured-custom and block-based application specified integrated circuit methodologies. We address the problem of how to perform the buffering of global multiterminal nets given an existing buffer block plan. We give provably good and heuristic algorithms for this problem. The method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals are satisfied. In addition, the algorithms allow more than one buffer to be inserted into any given connection and observe upper bounds and parity constraints on the number of buffers per connection. Most importantly, and unlike previous works on the problem, we take into account: 1) multiterminal nets; 2) multiple routing layers; 3) simultaneous buffered routing and compaction; and 4) buffer libraries. Our method outperforms existing algorithms for the problem, based on two-pin decompositions of the nets, and has been validated on top-level layouts extracted from a recent high-end microprocessor design.

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 structured-custom and block-based ASIC methodologies. Recent works by Cong, Kong and Pan [5] and Tang and Wong [18] give algorithms to solve the buffer block planning problem. In this paper, we address the problem of how to perform buffering of global multiterminal nets given an existing buffer block plan. We give a provably good algorithm based on a recent approach of Garg and Könemann [8] and Fleischer [7] (see also Albrecht [1] and Dragan et al. [6]). Our method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals - as well as wirelength upper bounds per connection - are satisfied. In addition, our algorithm allows more than one buffer to be inserted into any given connection and observes buffer parity constraints. Most importantly, and unlike previous works on the problem [5, 18, 6], we take into account multiterminal nets. Our algorithm outperforms existing algorithms for the problem [5, 6], which are based on 2-pin decompositions of the nets. The algorithm has been validated on top-level layouts extracted from a recent high-end microprocessor design.

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 methodologies. Recent works by Cong et al. (1999) and Tang and Wong (2000) give algorithms to solve the buffer block planning problem. In this paper we address the problem of how to perform buffering of global nets given an existing buffer block plan. Assuming that global nets have been already decomposed into two-pin connections, we give a provably good algorithm based on a recent approach of Garg and Konemann (1998) and Fleischer (1999). Our method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals-as well as wirelength upper bounds per connection-are satisfied. Our model allows more than one buffer to be inserted into any given connection. In addition, our algorithm observes buffer parity constraints, i.e., it will choose to use an inverter or a buffer (=co-located pair of inverters) according to source and destination signal parity. The algorithm outperforms previous approaches and has been validated on top-level layouts extracted from a recent high-end microprocessor design.

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 pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.

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 semisimplicial ordering of graphs. We present new characterizations of HHD-free graphs via m 3 -convexity and obtain some results known from [B. Jamison and S. Olariu, Adv. Appl. Math., 9 (1988), pp. 364--376] as corollaries. Moreover, we characterize weak bipolarizable graphs as the graphs for which the family of all m 3 -convex sets is a convex geometry. As an application of our results we present a simple efficient criterion for deciding whether a HHD-free graph contains a r-dominating clique with respect to a given vertex radius function r.

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 present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree problems on distance-hereditary graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 177–182, 1998

Recently in several papers, graphs with maximum neighborhood orderings were characterized and turned out to be algorithmically useful. This paper gives a unified framework for characterizations of those graphs in terms of neighborhood and clique hypergraphs which have the Helly property and whose line graph is chordal. These graphs are dual (in the sense of hypergraphs) to chordal graphs. By using the hypergraph approach in a systematical way new results are obtained, some of the old results are generalized, and some of the proofs are simplified.

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 r-packing sets. We prove that a homogeneously orderable graph G possesses an r-dominating clique if and only if for any pair of vertices x, y of G d(x, y) ≤ r(x) + r(y) + 1 holds where r : V → N is a given vertex function. Furthermore, we show that for homogeneously orderable graphs with r-dominating cliques the cardinality of a maximum strict r-packing set equals the cardinality of a minimum r-dominating clique provided the last parameter is not two. Finally, we present two efficient algorithms: The first one decides whether a given homogeneously orderable graph has an r-dominating clique and, if so, computes both a minimum r-dominating clique and a maximum strict r-packing set of the graph. The second one computes a minimum connected r-dominating set in a homogeneously orderable graph. © 1997 John Wiley & Sons, Inc. Networks 30: 121–131, 1997

Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex vr-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the standard graph distance. A subset $D \subseteq V$ is a clique r-dominating set of G if for every clique $C \in \cal C$ there is a vertex $u \in D$ which r-dominates C. A clique r-packing set is a subset $P \subseteq \cal C$ such that there are no two distinct cliques $C',C'\in P$ r-dominated by a common vertex of G. The clique r-domination problem is to find a clique r-dominating set with minimum size and the clique r-packing problem is to find a clique r-packing set with maximum size. The formulated problems include many domination and clique-transversal-related problems as special cases. In this paper an efficient algorithm is proposed for solving these problems on dually chordal graphswhich are a natural generalization of strongly chordal graphs. The efficient algorithm is mainly based on the tree structure and special vertex elimination orderings of dually chordal graphs. In some important particular cases where the algorithm works in linear time the obtained results generalize and improve known results on strongly chordal graphs.