Recently, large contents in the Internet have increased loads of contents servers, networks and data centers, which may degrade the quality of services. To overcome this problem, some mirror servers providing the same...
详细信息
ISBN:
(纸本)9781479963874
Recently, large contents in the Internet have increased loads of contents servers, networks and data centers, which may degrade the quality of services. To overcome this problem, some mirror servers providing the same contents are located on a network and a request is navigated to one of the mirror servers. A user must access to one of the servers and the hop length of a path from a user to a server should be short even during link failure. As it affects the performance, the location of the mirror servers is important. In this paper, we address the server location problem, which determines the location of the servers satisfying the following the constraint: any users can access servers within a small hop count even if some links fail. First, we formulate this problem and prove that it is NP-hard. Second, we present a polynomial-time algorithm for the case that the number of simultaneously failed links is restricted to one and the increase of the distance between a user node and servers during failure is restricted to be the number of nodes. Furthermore, we also present an approximation algorithm to solve this problem when the number of servers to be accessed is restricted to one and the number of simultaneously failed links is a constant positive integer, and we evaluate the performance by using some actual network topologies.
We consider a pairwise kidney exchange model. Roth et al. (2005) define priority matchings of the model and introduce a mechanism to derive them. In this paper, we re-examine the priority matching. First, we consider ...
详细信息
We consider a pairwise kidney exchange model. Roth et al. (2005) define priority matchings of the model and introduce a mechanism to derive them. In this paper, we re-examine the priority matching. First, we consider a general priority ordering where multiple patients may hold equal priority. We provide a characterization of the priority matchings by using the concept of alternating paths. Using the characterization, we examine the effect of a small change in the priority order on a set of priority matchings. Moreover, we provide an efficient method to find a priority matching. (C) 2014 Elsevier Inc. All rights reserved.
Graphs can be effectively used to represent relationships between objects such as social networks, web search engines and genome sequencing. In this paper, we deal with two variants of graph matching, the graph isomor...
详细信息
ISBN:
(纸本)9781509018949
Graphs can be effectively used to represent relationships between objects such as social networks, web search engines and genome sequencing. In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the prefix set of graph isomorphism. We propose polynomial-time exact algorithms for these problems on graphs with tree-like structure. These could be useful tools for big data processing.
The dominating induced matching problem is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This is known to be NP-complete in general. We develop a polynomial...
详细信息
We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of net...
详细信息
We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of network interdiction and graph theory research and are relevant to several practical optimization problems. The two different connectivity metrics that we consider regard the number of maximal connected components (which we attempt to maximize) and the largest component size (which we attempt to minimize). We develop optimal polynomial-time dynamic programming algorithms for solving these problems on tree structures and on series-parallel graphs, corresponding to each graph-connectivity metric. We also extend our discussion by considering node deletion costs, node weights, and solving the problems on generalizations of tree structures. Finally, we demonstrate the computational efficacy of our approach on randomly generated graph instances. (c) 2011 Wiley Periodicals, Inc. NETWORKS, 2012
The location problem is one kind of special type optimized problems .The Min-max weighted distance problem is a new class of location problem, its decision problem is a NP- Complete problem. In this paper, some approx...
详细信息
The location problem is one kind of special type optimized problems .The Min-max weighted distance problem is a new class of location problem, its decision problem is a NP- Complete problem. In this paper, some approximate algorithms are designed, designs a genetic algorithm by some properties of the problem, and gives the design and selection method of crossover operator, mutation operator and reproduction operator.
The k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G ...
详细信息
The k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most six vertices, it is known that 3-COLORING is polynomial-time solvable on H-free graphs whenever H is a linear forest, and NP-complete otherwise. By solving the missing case P-2 + P-3, we prove the same result for 4-COLORING provided that H is a fixed graph on at most five vertices. (c) 2012 Elsevier B.V. All rights reserved.
The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard and admits no K-approximation for any K > 1 in the general case (Xu et al. in IEEE/ACM Trans....
详细信息
The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard and admits no K-approximation for any K > 1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147-158, 2006). In this paper, we first show that Bhatia et al.'s NP-hardness proof (Bhatia et al. in J. Comb. Optim. 12:83-96, 2006), a claim of correction to Xu et al.'s proof (Xu et al. in IEEE/ACM Trans. Netw. 14:147-158, 2006), for the edge-disjoint Min-Min problem in the general undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in the proof of Bhatia et al. (J. Comb. Optim. 12:83-96, 2006). We then gave a correct proof of NP-hardness of this problem in undirected graphs. Finally we give a polynomial-time algorithm for the vertex disjoint Min-Min problem in planar graphs by showing that the vertex disjoint Min-Min problem is polynomially solvable in st-planar graph G=(V,E) whose corresponding auxiliary graph G(V,Ea(a){e(st)}) can be embedded into a plane, and a planar graph can be decomposed into several st-planar graphs whose Min-Min paths collectively contain a Min-Min disjoint-path pair between s and t in the original graph G. To the best of our knowledge, these are the first polynomialalgorithms for the Min-Min problems in planar graphs.
Three algorithms of Gram Schmidt type are given that produce orthogonal decompositions of finite d-dimensional symmetric, alternating, or Hermitian forms over division rings. The first uses d(3)/3 + O(d(2)) products i...
详细信息
Three algorithms of Gram Schmidt type are given that produce orthogonal decompositions of finite d-dimensional symmetric, alternating, or Hermitian forms over division rings. The first uses d(3)/3 + O(d(2)) products in Delta. Next, that algorithm is adapted in two new directions. One is a nearly optimal sequential algorithm whose complexity matches the complexity of matrix multiplication. The other is a parallel algorithm. (C) 2013 Elsevier Inc. All Tights reserved.
A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an ...
详细信息
A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the "three-in-a-tree" subroutine. (C) 2013 Elsevier Inc. All rights reserved.
暂无评论