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

18th International Symposium on algorithmics of Wireless Networks

作者： Mertzios, George B. Michail, Othon Skretas, George Spirakis, Paul G. Theofilatos, Michail Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Patras Comp Engn & Informat Dept Patras Greece

ISBN: (数字)9783031220500

ISBN: (纸本)9783031220494;9783031220500

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u(0) and operates in discrete time-steps, called slots. In every slot t >= 1, the process updates the current graph instance to generate the next graph instance G(t). The process first sets G(t) = G(t-1). Then, for every u is an element of V (G(t-1)), it adds at most one new vertex u' to V (G(t)) and adds the edge uu' to E(G(t)) alongside any subset of the edges {vu' vertical bar v is an element of V (G(t-1)) is at distance at most d - 1 from u in G(t-1)}, for some integer d >= 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(G(t)). Removed edges are called excess edges. G(t) is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth. Graph Growth Problem: Given a graph family F, we are asked to design a centralized algorithm that on any input target graph G is an element of F, will output such a process growing G, called a growth schedule for G. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges l used by the process. We show that the most interesting case is when d = 2 and that there is a natural trade-off between k and l. We begin by investigating growth schedules of l = 0 excess edges. On the positive side, we provide polynomial-time algorithms that decide whether a graph has growth schedules of k = logn or k = n - 1 slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for the problem of determining the minimum number of slots required to grow a graph with zero excess edges. In particular, we show that the problem (i) is NP-complete and (ii) for any e > 0, cannot be approximated within n(1/3-epsilon), unless P = NP. We then move our focus to the other extreme of the (

关键词： Temporal graph Cop-win graph Graph process polynomial-time algorithm Lower bound NP-complete Hardness result

来源：评论

学校读者我要写书评

暂无评论

Colouring Vertices of Triangle-Free Graphs 1

引用

36th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Dabrowski, Konrad Lozin, Vadim Raman, Rajiv Ries, Bernard Univ Warwick DIMAP Coventry CV4 7AL W Midlands England

ISBN: (数字)9783642169267

ISBN: (纸本)9783642169250

The VERTEX COLOURING problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it remains NP-complete even if we additionally exclude a graph F which is not a forest. We study the computational complexity of the problem in (K(3), F)-free graphs with F being a forest. From known results it follows that for any forest F on 5 vertices the VERTEX COLOURING problem is polynomial-time solvable in the class of (K3, F)-free graphs. In the present paper, we show that the problem is also polynomial-time solvable in many classes of (K3, F)-free graphs with F being a forest on 6 vertices.

关键词： Vertex colouring Triangle-free graphs polynomial-time algorithm Clique-width

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for k-Domination and Total k-Domination in Proper Interval Graphs 5th

Improved Algorithms for k-Domination and Total k</...

引用

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Chiarelli, Nina Hartinger, Tatiana Romina Alejandra Leoni, Valeria Lopez Pujato, Maria Ines Milanic, Martin Univ Primorska FAMNIT Glagoljaska 8 Koper 6000 Slovenia Univ Primorska IAM Muzejski Trg 2 Koper 6000 Slovenia Univ Nacl Rosario FCEIA Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina ANPCyT Buenos Aires DF Argentina

ISBN: (纸本)9783319961514;9783319961507

Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set, also known as a k-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, resp. total k-dominating set, in a given graph, are referred to as k-domination, resp. total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from recent work by Kang et al. (2017) that these two families of problems are solvable in time O(vertical bar V(G)vertical bar(6k+4)) in the class of interval graphs. In this work, we develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs. The algorithms run in time O(vertical bar V(G)vertical bar(3k)) for each fixed k >= 1 and are also applicable to the weighted case.

关键词： k-domination Total k-domination Proper interval graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithm for Server Allocation in Delay-Sensitive Internet-of-Things Monitoring Services

Algorithm for Server Allocation in Delay-Sensitive Internet-...

引用

International Conference on Computing, Networking and Communications (ICNC)

作者： Imanaka, Shoya Kawabata, Akio Chatterjee, Bijoy Chand Oki, Eiji Kyoto Univ Kyoto Japan Toyohashi Univ Technol Toyohashi Aichi Japan South Asian Univ Delhi India

ISBN: (纸本)9798350371000;9798350370997

This paper proposes a polynomial-time algorithm for a server allocation problem in delay-sensitive Internet-of-Things (IoT) monitoring services. The server allocation problem determines the appropriate servers to which the database and application are allocated to minimize the maximum delay between the latest update of reference data and the start of application processing for monitoring data. The proposed algorithm comprises two components. The initial phase involves the selection of usage servers for both the database and the application. Subsequently, the second phase entails matching each usage server and its corresponding IoT device. The proposed algorithm obtains an optimal allocation solution in polynomial time. Numerical results show that the proposed algorithm obtains the optimal solution faster than an integer linear programming approach.

关键词： server allocation problem Internet of things monitoring service polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Cooperative project scheduling with controllable processing times: a game theory framework

Cooperative project scheduling with controllable processing ...

引用

16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)

作者： Briand, Cyril Billaut, Jean-Charles Univ Toulouse LAAS CNRS F-31077 Toulouse 4 France

ISBN: (纸本)9781457700187

This paper considers a project-scheduling environment assuming that the activities of the project network are distributed among a set of actors (or agents). Activity durations are modeled as time intervals and are controllable, meaning that every actor is allowed to shorten the duration of some activities by adding extra-money. For performing the project, actors have to collaborate with each other intending to satisfy a desired project duration. In this work, every actor's payoff corresponds to a given ratio of the total customer's payment, which itself depends on the ability of the actors to achieve the project in time, provided daily penalty costs are applied in case of tardiness. This problem can be modeled as a game, where players (actors) have to select a strategy (a duration vector for their activities) intending to maximize their profit. In this paper, the focus is put on the modeling of this project game, and on the connections between various decision problems, arising either in decision or game theory. We also study the particular case where each activity is assigned to one specific agent and a polynomial-time algorithm is proposed for finding Nash equilibrium with the smallest project makespan.

关键词： Computer crashes Context Gold Job shop scheduling Nash equilibrium Nash equilibrium computational complexity controllable processing time cooperative project scheduling duration vector game theory game theory penalty cost polynomial-time algorithm project

来源：评论

学校读者我要写书评

暂无评论

Priority matchings revisited

引用

GAMES AND ECONOMIC BEHAVIOR 2014年 88卷 242-249页

作者： Okumura, Yasunori Hannan Univ Fac Econ Matsubara Osaka 5808502 Japan

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.

关键词： Matching Pairwise kidney exchange problem Roommate problem Priority mechanism polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient test for product states, with applications to quantum Merlin-Arthur games

An efficient test for product states, with applications to q...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Harrow, Aram W. Montanaro, Ashley Univ Bristol Dept Math Bristol BS8 1TH Avon England Univ Washington Dept Comp Sci & Engn Seattle WA USA Univ Bristol Dept Comp Sci Bristol Avon England Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB2 1TN England

ISBN: (纸本)9780769542447

We give a test that can distinguish efficiently between product states of n quantum systems and states which are far from product. If applied to a state vertical bar psi > whose maximum overlap with a product state is 1 - epsilon, the test passes with probability 1 - Theta(epsilon), regardless of n or the local dimensions of the individual systems. The test uses two copies of vertical bar psi >. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarising channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k) = QMA(2) for k >= 2. Building on a previous result of Aaronson et al, this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of (O) over tilde(root n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalisation of classical linearity testing.

关键词： SAT complexity-theoretic obstruction computability computational complexity depolarising channel game theory linearity testing maximum output purity polynomial-time algorithm probability probability product state product states quantum Merlin-Arthur quantum Merlin-Arthur game quantum algorithm quantum channel quantum computing quantum state quantum system separability tensor product tensors

来源：评论

学校读者我要写书评

暂无评论

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

A polynomial algorithm to find an independent set of maximum...

引用

17th ACM-SIAM Symposium on Discrete algorithms

作者： Lozin, Vadim V. Milanic, Martin Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

ISBN: (纸本)9780898716054

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.

关键词： Independent set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum Exploratory Equivalence in Trees

Maximum Exploratory Equivalence in Trees

引用

3rd International Conference on Innovative Network Systems and Applications (iNetSApp) held in conjunction with Federated Conference on Computer Science and Information Systems (FedCSIS)

作者： Furst, Luka Cibej, Uros Mihelic, Jurij Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 SI-1000 Ljubljana Slovenia

ISBN: (纸本)9788360810668

Many practical problems are modeled with networks and graphs. Their exploration is of significant importance, and several graph-exploration algorithms already exist. In this paper, we focus on a type of vertex equivalence, called exploratory equivalence, which has a great potential to speed up such algorithms. It is an equivalence based on graph automorphisms and can, for example, help us in solving the subgraph isomorphism problem, which is a well-known NP-hard problem. In particular, if a given pattern graph has nontrivial automorphisms, then each of its nontrivial exploratory equivalent classes gives rise to a set of constraints to prune the search space of solutions. In the paper, we define the maximum exploratory equivalence problem. We show that the defined problem is at least as hard the graph isomorphism problem. Additionally, we present a polynomial-time algorithm for solving the problem when the input is restricted to tree graphs. Furthermore, we show that for trees, a maximum exploratory equivalent partition leads to a globally optimal set of subgraph isomorphism constraints, whereas this is not necessarily the case for general graphs.

关键词： computational complexity search problems trees (mathematics) NP-hard problem general graphs graph automorphisms graph-exploration algorithms maximum exploratory equivalence problem nontrivial automorphisms polynomial-time algorithm search space subgraph isomorphism constraints tree graphs vertex equivalence Computational modeling Computers Data models Partitioning algorithms Search problems Software algorithms Tree graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient Domination for Some Subclasses of P₆-free Graphs in polynomial time 41st

Efficient Domination for Some Subclasses of P6</...

引用

41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Brandstaedt, Andreas Eschen, Elaine M. Friese, Erik Univ Rostock Inst Informat D-18051 Rostock Germany West Virginia Univ Morgantown WV USA Univ Rostock Inst Math Ulmenstr 69 D-18057 Rostock Germany

ISBN: (纸本)9783662531747;9783662531730

Let G be a finite undirected graph. A vertex dominates itself and all 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 such as P-7-free chordal graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set (MWIS) problem on the square of G. The complexity of the ED problem is an open question for P-6-free graphs and was open even for the subclass of P-6-free chordal graphs. In this paper, we show that squares of P-6-free chordal graphs that have an e.d. are chordal;this even holds for the larger class of (P-6, house, hole, domino)-free graphs. This implies that ED/WeightedED is solvable in polynomial time for (P-6, house, hole, domino)-free graphs;in particular, for P-6-free chordal graphs. Moreover, based on our result that squares of P-6- free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of (P-6, house)- free graphs ((P-6, bull)- free graphs, respectively) that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for (P-6, house)- free graphs and for (P-6, bull)- free graphs (the time bound for (P-6, house, hole, domino)- free graphs is better than that for (P-6, house)- free graphs). The complexity of the ED problem for P-6-free graphs remains an open question.

关键词： Efficient domination Chordal graphs Hole-free graphs (house,hole,domino)-free graphs P6-free graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：