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

IEEE 37th Annual Computer Software and Applications Conference (COMPSAC)

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

ISBN: (纸本)9780769549873

Large-volume contents distributed by a content delivery network (CDN) on the Internet increase load of content delivery servers and networks, which may degrade the quality of service. As a method to keep high quality service for CDN, some mirror servers providing the same content are located on a network and a request is navigated to one of the mirror servers. The network must offer connectivity between a user and servers with small distance even during link failures. In this paper, we address a network design method by protection of critical links whose failures significantly degrade the performance. The objective is to find the smallest number of the links to be protected so that a user can access servers with small increase of distance even if non-protected links fail. First, we formulate this problem and prove that it is NP-hard. Second, we present a polynomial-time algorithm to solve this problem when the number of simultaneously failed links is restricted to one. Furthermore, we evaluate the number of protected links of actual ISP network topologies by the algorithm and show the relationship between the number of protected links and the values of the parameters.

关键词： Network Graph theory Link failures Protection Distance NP-hard polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the Eulerian closed walk with precedence path constraints problem

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 899-906页

作者： Kerivin, H.L.M. Lacroix, M. Mahjoub, A.R. Department of Mathematical Sciences Clemson University Clemson SC 29634 O-326 Martin Hall United States Université Paris-Dauphine LAMSADE 75775 Paris Cedex 16 Place du Maréchal de Lattre de Tassigny France

The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the paths are arc-disjoint. We also give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case. © 2010 Elsevier B.V.

关键词： Eulerian closed walk NP-completeness polynomial-time algorithm Precedence path constraints

来源：评论

学校读者我要写书评

暂无评论

Independent Sets of Maximum Weight in Apple-Free Graphs

引用

19th Annual International Symposium on algorithms and Computation (ISAAC)

作者： Brandstaedt, Andreas Klembt, Tilo Lozin, Vadim V. Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ Warwick DIMAP Math Inst Coventry CV4 7AL W Midlands England Univ Degli Studi G Annunzio Dipartimento Sci I-65121 Pescara Italy

ISBN: (纸本)9783540921813

We present the first polynomial-time algorithm to solve the Maximum "Weight Independent Set problem for apple-free graphs, which is a, common generalization of several important classes where the problem can be solved efficiently, suet) as claw-free graphs, chordal graphs and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free;the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.

关键词： Maximum independent set clique separators modular decomposition polynomial-time algorithm claw-free graphs apple-free graphs

来源：评论

学校读者我要写书评

暂无评论

Characterising Chordal Contact B₀-VPG Graphs 1

引用

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Bonomo, Flavia Pia Mazzoleni, Maria Leonardo Rean, Mariano Ries, Bernard Univ Buenos Aires Dept Computac Fac Ciencias Exactas & Nat Buenos Aires DF Argentina Univ Buenos Aires CONICET Inst Invest Ciencias Computac ICC Buenos Aires DF Argentina Univ Nacl La Plata Dept Matemat Fac Ciencias Exactas La Plata Buenos Aires Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Fribourg Fribourg Switzerland

ISBN: (数字)9783319961514

ISBN: (纸本)9783319961514;9783319961507

A graph G is a B-0-VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact B-0-VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B-0-VPG graphs within the class of chordal graphs and provide a polynomial-time algorithm for recognising these graphs.

关键词： Vertex intersection graphs Contact B-0-VPG graphs Forbidden induced subgraphs Chordal graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles 21st

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint...

引用

21st International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Kobayashi, Yusuke Kyoto Univ Res Inst Math Sci Kyoto 6068502 Japan

ISBN: (纸本)9783030457716;9783030457709

The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give a first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomialtime algorithm for the weighted T-free 2-matching problem.

关键词： Triangle-free 2-matchings b-factors Extended formulation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Clustering with Queries under Semi-Random Noise 35

Clustering with Queries under Semi-Random Noise

引用

35th Conference on Learning Theory (COLT)

作者： Del Pia, Alberto Ma, Mingchen Tzamos, Christos Univ Wisconsin Madison Madison WI 53706 USA

The seminal paper by Mazumdar and Saha (2017a) introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the proposed methods depend crucially on knowing the exact probabilities of errors of the underlying fully-random oracle. In this work, we develop robust learning methods that tolerate general semi-random noise obtaining qualitatively the same guarantees as the best possible methods in the fully-random model. More specifically, given a set of n points with an unknown underlying partition, we are allowed to query pairs of points u;v to check if they are in the same cluster, but with probability p, the answer may be adversarially chosen. We show that information theoretically O(nk log n/(1 -2 p)(2) queries suffice to learn any cluster of sufficiently large size. Our main result is a computationally efficient algorithm that can identify large clusters with O(nk log n/((1 - 2p)(2)) + poly (log n, k, 1/1 -2(p)) queries, matching the guarantees of the best known algorithms in the fully-random model. As a corollary of our approach, we develop the first parameter-free algorithm for the fully-random model, answering an open question in Mazumdar and Saha (2017a).

关键词： Clustering Semi-random noise polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Axiomatization of Implication for Probabilistic Independence and Unary Variants of Marginal Identity and Marginal Distribution Equivalence 13th

Axiomatization of Implication for Probabilistic Independence...

引用

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

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

ISBN: (纸本)9783031569395;9783031569401

We consider probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. This paper offers a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.

关键词： Complete axiomatization Probabilistic independence Marginal distribution equivalence Marginal identity polynomial-time algorithm Probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

Complexity of linear programming

引用

Operations Research Letters 1982年第2期1卷 59-62页

作者： Traub, J.F. Woźniakowski, H. Department of Computer Science Columbia University New York NY 10027 United States Institute of Informatics University of Warsaw Warsaw Poland Department of Computer Science Columbia University New York NY 10027 United States

The complexity of linear programming is discussed in the "integer" and "real number" models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation. Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all "reasonable" models of computation. © 1982.

关键词： Computational complexity ellipsoid algorithm linear inequalities linear programming models of computation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

New polynomial Cases of the Weighted Efficient Domination Problem

New Polynomial Cases of the Weighted Efficient Domination Pr...

引用

38th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Brandstaedt, Andreas Milanic, Martin Nevries, Ragnar Univ Rostock Inst Informat D-18051 Rostock Germany Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

ISBN: (纸本)9783642403132;9783642403125

Let G be a finite undirected graph. A vertex dominates itself and its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes. In particular, the ED problem remains NP-complete for 2P(3)-free graphs and thus for P-7-free graphs. We show that the weighted version of the problem (abbreviated WED) is solvable in polynomial time on various subclasses of P-7-free graphs, including (P-2 + P-4)-free graphs, P-5-free graphs and other classes. Furthermore, we show that a minimum weight e.d. consisting only of vertices of degree at most 2 (if one exists) can be found in polynomial time. This contrasts with our NP-completeness result for the ED problem on planar bipartite graphs with maximum degree 3.

关键词： efficient domination P-k-free graphs polynomial-time algorithm robust algorithm

来源：评论

学校读者我要写书评

暂无评论

Vertex Cover at Distance on H-Free Graphs 32nd

Vertex Cover at Distance on <i>H</i>-Free Graphs

引用

32nd International Workshop on Combinatorial algorithms (IWOCA)

作者： Dallard, Clement Krbezlija, Mirza Milanic, Martin Univ Primorska FAMNIT Koper Slovenia Univ Primorska IAM Koper Slovenia

ISBN: (纸本)9783030799878;9783030799861

The question of characterizing graphs H such that the VERTEX COVER problem is solvable in polynomial time in the class of H-free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distance-based generalization of vertex cover called distance-k vertex cover, for any positive integer k. In this problem the task is to determine, given a graph G and an integer l, whether G contains a set of at most l vertices such that each edge of G is at distance at most k from a vertex in the set. We show that for all k >= 1 and all graphs H, the distance-k vertex cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of P2k+2 + sP(max{k,2}) for some s >= 0, and NP-complete otherwise.

关键词： Distance-k Vertex Cover H-free graph NP-completeness polynomial-time algorithm Dichotomy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：