检索结果-内蒙古大学图书馆

8th International Conference on Intelligent Networking and Collaborative Systems (INCoS)

作者： Irie, Daishi Miwa, Hiroyoshi Kwansei Gakuin Univ Grad Sch Sci & Technol 2-1 Gakuen Sanda Hyogo 6691337 Japan

ISBN: (纸本)9781509041237

It is important for network service providers to design and operate reliable network which is robust against network failures. Especially, a network must be sufficiently connected, even if link failures occur. There are many methods to design a robust network. One is a method based on a server location problem. As the location of mirror servers affects the performance of a content delivery service, it is necessary to find a better server placement. Another method is based on link protection. It is desirable to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, link protection costs are high;therefore, it is important to find the smallest number of links to be protected so that a network resulting from failures of any non-protected links provides users connectivity. In this paper, we address a network design method by combining server placement method and link protection method. Even if a network cannot be made reliable simply by server placement method or simply by link protection method, the combination of them may make the network reliable. Thus, our purpose is to find a server placement and a set of links to be protected such that, even if any non-protected links fail, all connected components include specified servers in the resulting network. First, we formulate this reliable network design method by combining server placement method and link protection method and show that this problem is NP-hard. In addition, we propose a polynomial-time algorithm to solve the problem that the number of the protected links is restricted to zero, and a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we evaluate the algorithm by applying it to the topology of actual networks and show that the proposed algorithms work well.

关键词： server placement link protection network design connectivity optimization NP-hard polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Shortest Even Cycle Problem Is Tractable 2022

The Shortest Even Cycle Problem Is Tractable

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bjorklund, Andreas Husfeldt, Thore Kaski, Petteri Lund Univ Lund Sweden IT Univ Copenhagen Copenhagen Denmark Aalto Univ Dept Comp Sci Espoo Finland

ISBN: (纸本)9781450392648

Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a directed graph in polynomial time was open for more than two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004;announced jointly at STOC 1997) gave an efficiently testable structural characterisation of even-cycle-free directed graphs. Methodologically, our algorithm relies on the standard framework of algebraic fingerprinting and randomized polynomial identity testing over a finite field, and in fact relies on a generating polynomial implicit in a paper of Vazirani and Yannakakis (Discrete Appl. Math. 1989) that enumeratesweighted cycle covers by the parity of their number of cycles as a difference of a permanent and a determinant polynomial. The need to work with the permanent- known to be #P-hard apart from a very restricted choice of coefficient rings (Valiant, Theoret. Comput. Sci. 1979)-is where our main technical contribution occurs. We design a family of finite commutative rings of characteristic 4 that simultaneously (i) give a nondegenerate representation for the generating polynomial identity via the permanent and the determinant, (ii) support efficient permanent computations by extension of Valiant's techniques, and (iii) enable emulation of finite-field arithmetic in characteristic 2. Here our work is foreshadowed by that of Bjorklund and Husfeldt (SIAM J. Comput. 2019), who used a considerably less efficient commutative ring design-in particular, one lacking finite-field emulation-to obtain a polynomial-time algorithm for the shortest two disjoint paths problem in undirected graphs. Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alon and Yuster (J. ACM 2013), we also show how ideas from the nested dissect

关键词： directed graph shortest even cycle shortest two disjoint paths parity cycle cover permanent polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences 1

引用

12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)

作者： Hirvonen, Minna Univ Helsinki Dept Math & Stat Helsinki Finland

ISBN: (数字)9783031113215

ISBN: (纸本)9783031113215;9783031113208

We study functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables x and y are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable x is the same as the corresponding multiset for y. We present a sound and complete axiomatization and a polynomial-time algorithm for the implication problem for the class of these dependencies, and show that this class has Armstrong relations.

关键词： Armstrong relations Complete axiomatization Functional dependence Marginal distribution equivalence polynomial-time algorithm Probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms and Hardness Results for Geometric Red-Blue Hitting Set Problem

Exact Algorithms and Hardness Results for Geometric Red-Blue...

引用

3rd International Joint Conference on Theoretical Computer Science (IJTCS) / 16th International Conference on Frontiers of algorithmic Wisdom (FAW)

作者： Madireddy, Raghunath Reddy Nandy, Subhas C. Pandit, Supantha Birla Inst Technol & Sci Pilani Hyderabad Campus Hyderabad Telangana India Indian Stat Inst Kolkata India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

ISBN: (纸本)9783031207952;9783031207969

We study geometric variations of the Red-Blue Hitting Set problem. Given two sets of objects R and B, colored red and blue, respectively, and a set of points P in the plane, the goal is to find a subset P ' subset of P of points that hits all blue objects in B while hitting the minimum number of red objects in R. We study this problem for various geometric objects. We present a polynomial-time algorithm for the problem with intervals on the real line. On the other hand, we show that the problem is NP-hard for axis-parallel unit segments. Next, we study the problem with axis-parallel rectangles. We give a polynomial-time algorithm for the problem when the rectangles are anchored on a horizontal line. The problem is shown to be NP-hard when all the rectangles intersect a horizontal line. Finally, we prove that the problem is APX-hard when the objects are axis-parallel rectangles containing the origin of the plane, axis-parallel rectangles where every two rectangles intersect exactly either zero or four times, axis-parallel line segments, axis-parallel strips, and downward shadows of segments. To achieve these APX-hardness results, we first introduce a variation of the Red-Blue Hitting Set problem in a set system, called the Special-Red-Blue Hitting Set problem. We prove that the Special-Red-Blue Hitting Set problem is APX-hard and we provide an encoding of each class of objects mentioned above as the Special-Red-Blue Hitting Set problem.

关键词： Special Red-Blue Hitting Set Anchored rectangles Intervals polynomial-time algorithm NP-hard APX-hard

来源：评论

学校读者我要写书评

暂无评论

Network Design Method Based on Link Protection Taking Account of the Connectivity and Distance Between Sites 8

Network Design Method Based on Link Protection Taking Accoun...

引用

8th International Conference on Intelligent Networking and Collaborative Systems (INCoS)

作者： Yamasaki, Tsuyoshi Anan, Makoto Miwa, Hiroyoshi Kwansei Gakuin Univ Sch Sci & Technol 2-1 Gakuen Sanda Hyogo 6691337 Japan

ISBN: (纸本)9781509041237

High reliability is required in networks, and it is important to build robust networks that are tolerant to network failures. In content delivery services in particular, service interruptions due to disconnection of communication paths between the server and nodes that receive the service must be avoided. Content delivery services use a master server that contains the original content and multiple edge-servers (mirror servers) that hold copies of the content so that communication paths exist between the master server and the edge-servers even in the event of a failure. In addition to the guarantee of network connectivity, large increases in path lengths when changing from the paths used during normal operation to alternative paths in the event of a failure must be avoided from the viewpoint of suppressing degradation of the communication quality and the possibility of congestion. However, building such high-reliability networks involves huge costs. Therefore, it is considered necessary to devise a network design that can realize continuity of communication between the master server and the edge-servers by suppressing sudden increases in path length, even if a failure occurs. In this paper, we formulate a network design problem and show that it is NP-hard. We also design a polynomial-time approximation algorithm for the case where the number of failed links is constant, and we evaluated its performance in various actual network topologies.

关键词： Network Graph theory Computational complexity Link failures Link protection NP-hard polynomial-time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Edge Monitoring Problem on Interval Graphs

引用

Electronic Notes in Discrete Mathematics 2016年 54卷 331-336页

作者： Bagan, Guillaume Beggas, Fairouz Haddad, Mohammed Hheddouci, Hamamache LIRIS UMR 5205 CNRS Claude Bernard Lyon 1 University Villeurbanne France

Edge monitoring is a simple and effective mechanism for the security of wireless sensor networks. The idea is to award specific roles (monitors) to some sensor nodes of the network. A node v monitors an edge e if both extremities together with v form a triangle in the graph. Given an edge colored graph G=(V,E,c), the color c(e) is a positive integer representing the number of monitors needed by the edge e. The problem is to seek a minimum cardinality subset of monitors S such that every edge e in the graph is monitored by at least c(e) vertices in S. If vertices of G are weighted, the objective then is to minimize the total weight of vertices of S and the problem is called weighted edge monitoring problem. In this paper, we present a polynomial-time algorithm for finding an edge monitoring set of minimum weight in interval graphs. © 2016 Elsevier B.V.

关键词： complexity Edge monitoring interval graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting Critical Protected Links to Keep Connectivity to Servers Against Link Failures 7

Detecting Critical Protected Links to Keep Connectivity to S...

引用

7th International Conference on New Technologies, Mobility and Security (NTMS)

作者： Irie, Daishi Kurimoto, Shinya Miwa, Hiroyoshi Kwansei Gakuin Univ Sch Sci & Technol 2-1 Gakuen Sanda Hyogo 6691337 Japan

ISBN: (纸本)9781479987849

It is important for service providers to design and operate reliable network which is robust against network failures. Especially, a network must be sufficiently connected, even if link failures occur. It is desirable to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, link protection needs much cost;therefore, it is important to find the smallest number of links to be protected so that a network resulting from failures of any non-protected links provides users connectivity. In this paper, we focus on the criteria that all connected components include specified servers in a resulting network after links fail. Our purpose is to find the links to be protected such that, even if any non-protected links fail, all connected components in the resulting network include the servers. First, we formulate this link protection problem and prove that this problem is NP-hard. Next, we present a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we present a polynomial-time approximation algorithm with the approximation ratio of a constant, the number of the simultaneous link failures. In addition, we apply the approximation algorithms to the topology of actual networks and evaluate the approximation ratio. The results indicate that the approximation ratio in the actual networks is much smaller than the theoretical upper bound. It follows that our algorithms are efficient when we determine protected links in an actual network.

关键词： link protection network design connectivity optimization NP-hard approximation algorithm polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Routing for Bidirectional Flows with Network Coding in Asymmetric Wireless Networks

Optimal Routing for Bidirectional Flows with Network Coding ...

引用

International Conference on Computing, Networking and Communications (ICNC)

作者： Dehkordi, Hooman Reisi Libman, Lavy Univ New S Wales Sch Comp Sci & Engn Sydney NSW 2052 Australia

ISBN: (纸本)9781479923588

Wireless network coding has attracted considerable research interest due to its promise of delivering increased capacity with high energy efficiency via the transmission of packet combinations from multiple flows. Much of this interest is based on the approach of the COPE protocol [1], which uses broadcasts of XOR combinations of packets to reduce the number of transmissions required, as long as they can be immediately decoded at the next hop of the respective flows. In this paper, we focus on the question of optimal routing of a bidirectional flow between a single pair of endpoints in the presence of wireless network coding, where the links are imperfect and have positive, and possibly asymmetric, packet erasure probabilities. Unlike previous studies, we explicitly allow packets to be forwarded in the network in a coded form, to be ultimately decoded by the destinations. We pose the optimization problem of finding the optimal path in each direction, so as to minimize the expected overall number of transmissions required to successfully deliver one packet in each direction of the flow, and present a polynomial-time algorithm for its solution. In particular, we demonstrate that, counterintuitively, it is possible for the optimal pair of paths for the bidirectional flow to have an overlapping section where packets are transmitted in the same direction, and illustrate the importance of this possibility by evaluating the performance of optimal network coding paths in random and asymmetric mesh topologies of between 9 and 36 nodes.

关键词： network coding optimisation polynomials telecommunication network routing telecommunication network topology wireless channels COPE protocol XOR combinations asymmetric mesh topology asymmetric wireless networks bidirectional flows multiple flows network coding optimal routing optimization problem packet combinations packet erasure probability polynomial-time algorithm random mesh topology Educational institutions Measurement Principal component analysis

来源：评论

学校读者我要写书评

暂无评论

Finding dense subgraphs efficiently

Finding dense subgraphs efficiently

引用

International Conference on Foundations of Computer Science (FCS 05)

作者： Faragó, A Univ Texas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75083 USA

ISBN: (纸本)1932415718

In a number of applications we want to find a densest subgraph in an input graph. The complexity of this task depends on how density is defined. If density means the ratio of the number of edges and the number of vertices in the subgraph, then the algorithmic problem has long been known efficiently solvable. On the other hand, the task becomes NP-hard with closely related but somewhat modified concepts of density. To capture many different densiry concepts of interest in a common model, we define a general concept of density, called G-density. Looking for a subgraph with maximum TG-density means that we search for a subgraph G' in the input graph, such that G' has the highest number of G-type subgraphs relative to the number of vertices in G'. Here G is an arbitrary class of graphs, which determines which subgraphs are counted in computing the density This concept subsumes many natural and important particular density concepts. Our main result is that for any fixed class G, a subgraph of maximum G-density can be found in polynomial time in any input graph.

关键词： graph subgraph subgraph with maximum density polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting Critical Links for Keeping Shortest Distance from Clients to Servers during Failures

Detecting Critical Links for Keeping Shortest Distance from ...

引用

12th IEEE/IPSJ International Symposium on Applications and the Internet (SAINT) / IEEE Annual Signature Conference on Computer Software and Applications (COMPSAC)

作者： Maeda, Nao Miwa, Hiroyoshi Kwansei Gakuin Univ Nishinomiya Hyogo 6691337 Japan

ISBN: (纸本)9780769547374

Recently, large-volume contents distributed by a content delivery service (CDS) on the Internet increase load of content delivery servers and networks, which is at the risk for degradation of quality of service. To overcome this problem, some mirror servers providing the same content are located on a network, and a request is navigated to one of the mirror servers. A reliable CDS must offer connectivity between a user and servers with small hop count even during link failure. Therefore, the introduction of mirror servers causes a new problem such as a high reliable network design which is appropriate for CDS. In this paper, we address a reliable network design problem by protection of critical links whose failures significantly degrade performance. The objective is to find the smallest number of the links to be protected so that all users can access servers within a small hop count even if non-protected links fail. First, we formulate this problem and prove that it is NP-hard. Second, we make clear the conditions that the problem is solvable in polynomial time. Specifically, we present a polynomial-time algorithm to solve the problem when the number of simultaneously failed link is restricted to one. Furthermore, we show that the problem can be solved also in polynomial time when hop count is restricted to one.

关键词： Network Graph theory Computational complexity Link failures Link protection Connectivity NP-hard polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：