In this paper, we introduce a natural class of multigraphs called hierarchical-scale-free (HSF) multigraphs, and consider constant-time testability on the class. We show that a very wide subclass of HSF is hyperfinite. Based on this result, an algorithm for a deterministic partitioning oracle can be constructed. We conclude by showing that every property is constant-time testable on the above subclass of HSF. This algorithm utilizes findings by Newman and Sohler of STOC'11. However, their algorithm is based on a bounded-degree model, while it is known that actual scale-free networks usually include hubs, which have a very large degree. HSF is based on scale-free properties and includes such hubs. This is the first universal result of constant-time testability on a class of graphs made by a model of scale-free networks, and it has the potential to be applicable on a very wide range of scale-free networks.

We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices $n$. We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity $O(d^2)$, where $d$ is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error $\epsilon n$ for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to $d$ and $\frac{1}{\epsilon}$. Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least $\Omega(n)$ queries.

This paper studies approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the degree bound, respectively. This paper presents an algorithm to approximate the size of some maximal independent set with additive error ε n whose running time is O(d2). Using this algorithm, it also shows that there are approximation algorithms for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/ε. Its approximation algorithm for the maximum matching problem can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. On the contrary, it also shows that every one-sided error tester for the property requires at least Ω(n) queries.

In this article, we consider isolated cliques and isolated dense subgraphs. For a given graph G , a vertex subset S of size k (and also its induced subgraph G ( S )) is said to be c -isolated if G ( S ) is connected to its outside via less than ck edges. The number c is sometimes called the isolation factor . The subgraph appears more isolated if the isolation factor is smaller. The main result in this work shows that for a fixed constant c , we can enumerate all c -isolated maximal cliques (including a maximum one, if any) in linear time. In more detail, we show that, for a given graph G of n vertices and m edges, and a positive real number c , all c -isolated maximal cliques can be enumerated in time O ( c 4 2 2c m ). From this, we can see that: (1) if c is a constant, all c -isolated maximal cliques can be enumerated in linear time, and (2) if c = O (log n ), all c -isolated maximal cliques can be enumerated in polynomial time. Moreover, we show that these bounds are tight. That is, if f ( n ) is an increasing function not bounded by any constant, then there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superlinear in n + m . Furthermore, if f ( n ) = ω(log n ), there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superpolynomial in n + m . We next introduce the idea of pseudo-cliques. A pseudo-clique having an average degree α and a minimum degree β, denoted by PC (α,β), is a set V ′ ⊆ V such that the subgraph induced by V ′ has an average degree of at least α and a minimum degree of at least β. This article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. Especially, we show the following results, where k is the number of vertices of the isolated pseudo-cliques: (1) For any ϵ > 0 there is a graph of n vertices for which the number of 1-isolated PC ( k - (log k ) 1 + ϵ , k /(log k ) 1 + ϵ ) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all c -isolated PC ( k - log k , k /log k ), for any constant c .

Abstract Let G = (V, E) be an undirected multigraph, where V and E are a set of vertices and a set of edges, respectively. Let k and l be fixed nonnegative integers. This paper considers location problems of finding a minimum‐size vertex‐subset S ⊆ V such that for each vertex x ∈ V the vertex‐connectivity between S and x is greater than or equal to k and the edge‐connectivity between S and x is greater than or equal to l. For the problem with edge‐connectivity requirements, that is, k = 0, an O(L(|V|, |E|, l)) time algorithm is already known, where L(|V|, |E|, l) is the time to find all h‐edge‐connected components for h = 1, 2, … , l and O(L(|V|, |E|, l)) = O(|E| + |V|2 + |V|min{|E|, l|V|}min{l, |V|}) is known. In this paper, we show that the problem with k ≥ 3 is NP‐hard even for l = 0. We then present an O(L(|V|, |E|, l)) time algorithm for 0 ≤ k ≤ 2 and l ≥ 0. Moreover, we prove that the problem parameterized by the size of S is fixed‐parameter tractable (FPT) for k = 3 and l ≥ 0. © 2002 Wiley Periodicals, Inc.

In this paper, we propose a slot assignment scheme for integrated voice and data traffic in reservation multiple access protocols. In the proposed scheme, a voice packet does not contend with a data packet and takes over the slot which is previously assigned to a data packet. Thus, a larger number of voice terminals can be accommodated without degradation of quality and throughput even in the situation that data were integrated. We evaluate the voice packet dropping probability, throughput and packet delay through computer simulation. The results show that the proposed scheme has better performance than the conventional PRMA and DQRUMA systems.

Let G = (V, E) be a graph where V and E are a set of nodes and a set of edges, respectively. Let X = {V1, V2, …, Vp}, Vi ⊆ V be a family of node-subsets. Each node-subset Vi is called an area, and a pair of G and X is called an area graph. A node ν ∈ V and an area Vi ∈ X are called k-NA (node-to-area)-connected if the minimum size of a cut separating ν and Vi is at least k. We say that an area graph (G, X) is k-NA-edge-connected when each ν ∈ V and Vi ∈ X are k-NA-edge-connected. This paper gives a necessary and sufficient condition for a given (G, X) to be k-NA-edge-connected: (G, X) is k-NA-edge-connected iff, for all positive integers h ≤ k, every h-edge-connected component of G includes at least one node from each area or has at least k edges between the component and the rest of the nodes. This paper also studied the Minimum Area Augmentation Problem, i.e., the problem of determining whether or not a given area graph (G, X) is k-NA-edge-connected and of choosing the minimum number of nodes to be included in appropriate areas to make the area graph k-NA-edge-connected (if (G, X) is not k-NA-edge-connected). This problem can be regarded as one of the location problems, which arises from allocating service-nodes on multimedia networks. We propose an O(|E| + |V|2 + L′ + min {|E|, k|V|} min {k|V|, k + |V|2}) time algorithm for solving this problem, where L′ is a space required to represent output areas. For a fixed k, this algorithm also runs in linear time when the h-edge-connected components of G are available for all h = 1, 2, …, k. © 1998 John Wiley & Sons, Inc. Networks 31: 157–163, 1998