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

When Can Graph Hyperbolicity be Computed in Linear time?

algorithmICA 2019年第5期81卷 2016-2045页

作者： Fluschnik, Till Komusiewicz, Christian Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Talmon, Nimrod TU Berlin Fak 4 Algorithm & Computat Complex Berlin Germany Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Durham Dept Comp Sci Durham England Ben Gurion Univ Negev Beer Sheva Israel

Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms used in practice for computing the hyperbolicity number of an n-vertex graph have running time O(n(4)). Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2(O(k)) + O(n + m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential time Hypothesis (SETH) fails, there is no 2(o(k)) . n(2-epsilon)-time algorithm for every epsilon > 0.

关键词： Parameterized complexity polynomial-time algorithm FPT in P Strong Exponential time Hypothesis Vertex cover number Cographs

来源：评论

学校读者我要写书评

暂无评论

On Computational Complexity of Pipe Puzzles

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2019年第9期E102A卷 1134-1141页

作者： Shirayama, Takumu Shigemura, Takuto Otachi, Yota Miyazaki, Shuichi Uehara, Ryuhei Appci Corp Tokyo 1620067 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138654 Japan Kumamoto Univ Fac Adv Sci & Technol Kumamoto 8608555 Japan Kyoto Univ Acad Ctr Comp & Media Studies Kyoto 6068501 Japan JAIST Sch Informat Sci Nomi 9231292 Japan

In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle;the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.

关键词： pipe puzzle NP-completeness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast solution of single-machine scheduling problem with embedded jobs

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期782卷 91-106页

作者： Vakhania, Nodari UAEMor Ctr Invest Ciencias Cuernavaca Morelos Mexico

We present a fast polynomial-time algorithm for single-machine scheduling problem with release times (r(j)), processing times (p(j)) and due dates (d(j)) with the objective to minimize the maximum job lateness. The general setting is strongly NP-hard. We expose a particular embedded structure that typically possess a subset of jobs in an instance of the problem. We establish useful properties of the problem instances that tolerate this structure, i.e., in such an instance no subset of embedded jobs overlaps in time with the jobs that do not belong to that subset. Relying on these properties, our algorithm finds an optimal solution for the corresponding class of problem instances. Whether a given problem instance is tolerant of the revealed embedded structure becomes known during the execution of the algorithm. Nevertheless, some sufficient conditions in terms of job parameters can a priori be given. One such a condition is that for any pair of jobs j and i with r(i) > r(j) and d(i) < d(j), d(i) - r(j) - p(j) <= d(i) - r(i) - p(i), and if r(i) + p(i) >= r(j) + p(j), then d(i) >= d(j). As we show, our setting remains powerful enough to model important real-life applications. (C) 2019 Elsevier B.V. All rights reserved.

关键词： polynomial-time algorithm Single-machine scheduling Release time Due date Lateness time complexity

来源：评论

学校读者我要写书评

暂无评论

Load Balancing User Association in Millimeter Wave MIMO Networks

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2019年第6期18卷 2932-2945页

作者： Alizadeh, Alireza Vu, Mai Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA

User association is necessary in dense millimeter wave (mmWave) networks to determine which base station a user connects to in order to balance base station loads and maximize a network utility. Given that mmWave connections are highly directional and vulnerable to small channel variations, user association changes these connections and hence significantly affects the network interference and consequently the users' instantaneous rates. In this paper, we introduce a new load balancing user association scheme for mmWave MIMO cellular networks which consider these dependencies. We formulate the user association problem as mixed integer nonlinear programming and design a polynomial-time algorithm, called worst connection swapping (WCS), to find a near-optimal solution. Simulation results confirm that the proposed user association scheme improves network performance significantly by adjusting the interference according to the association, and under the max-min fairness, also enhances cell-edge users' transmission rates. We also show how the proposed algorithm can be applied under mobility. Furthermore, the proposed WCS algorithm outperforms other generic algorithms for combinatorial programming such as the genetic algorithm in both accuracy and speed at several orders of magnitude faster, and for small networks, where exhaustive search is possible, it reaches the optimal solution.

关键词： User association mmWave MIMO systems load balancing MINLP polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A study on load-balanced variants of the bin packing problem

引用

DISCRETE APPLIED MATHEMATICS 2019年 264卷 4-14页

作者： Castro-Silva, D. Gourdin, E. Ecole Polytech Palaiseau France Orange Labs Lannion France

We consider several extensions of the fractional bin packing problem, a relaxation of the traditional bin packing problem where the objects may be split across multiple bins. In these extensions, we introduce load-balancing constraints imposing that the share of each object which is assigned to a same bin must be equal. We propose a Mixed-Integer Programming (MIP) formulation and show that the problem becomes NP-hard if we limit to at most 3 the number of bins across which each object can be split. We then consider a variant where the balanced allocations of objects to bins may be done in successive rounds;this problem was inspired by telecommunication applications, and may be used to model simple Live Streaming networks. We show that two rounds are always sufficient to completely assign all objects to the bins and then provide an optimal polynomial-time allocation algorithm for this problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Bin packing Load balancing Mixed-integer models polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting strong cliques

引用

DISCRETE MATHEMATICS 2019年第9期342卷 2738-2750页

作者： Hujdurovic, Ademir Milanic, Martin Ries, Bernard Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia Univ Fribourg Dept Informat Bd Perolles 90 CH-1700 Fribourg Switzerland

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs. (C) 2019 Published by Elsevier B.V.

关键词： Strong clique Weakly chordal graph Line graph Cubic graph NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A dichotomy for weighted efficient dominating sets with bounded degree vertices

引用

INFORMATION PROCESSING LETTERS 2019年 142卷 30-34页

作者： Brandstaedt, Andreas Milanic, Martin Univ Rostock Inst Informat D-18051 Rostock Germany Univ Primorska IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia

In a finite undirected graph G, a vertex v dominates itself and its neighbors. A vertex set D is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Effiderit Domination (ED) problem, which asks for the existence of an e.d.s. in G, is well known to be NP-complete for graphs of maximum degree 3. We say that an e.d.s. D of G is k-bounded (k-b.e.d.s. for short) if the degree of every vertex in D is at most k in G. The task of the k-Bounded Weighted Efficient Domination (k-BWED) problem is to determine whether a given vertex-weighted graph G admits a k-b.e.d.s., and if so, to compute one of minimum weight. It easily follows from the NIA-completeness of ED for graphs of maximum degree 3 that the k-BWED problem is NP-complete for every k > 3, and clearly, the k-BWED problem is solvable in linear time for k < 1. In this note, we show that the 2-BWED problem is solvable in time 0(1V(G)1(11/(G)1+ IE(G)I)), thus obtaining a dichotomy of the complexity status of k-BWED over all k > 0. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Weighted efficient domination Bounded degree vertices k-Bounded Weighted Efficient Domination polynomial-time algorithm Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling Mutual Exclusion Accesses in Equal-Length Jobs

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2019年第2期6卷 1–26页

作者： Kagaris, Dimitri Dutta, Sourav Southern Illinois Univ Elect & Comp Engn Dept 1230 Lincoln Dr Carbondale IL 62901 USA

A fundamental problem in parallel and distributed processing is the partial serialization that is imposed due to the need for mutually exclusive access to common resources. In this article, we investigate the problem of optimally scheduling (in terms of makespan) a set of jobs, where each job consists of the same number L of unit-duration tasks, and each task either accesses exclusively one resource from a given set of resources or accesses a fully shareable resource. We develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of jobs and for any number of resources for the case of L = 2. In the notation commonly used for job-shop scheduling problems, this result means that the problem J vertical bar d(ij) = 1, n(j) =2 vertical bar C-max ax is polynomially solvable, adding to the polynomial solutions known for the problems J2 vertical bar n(j) <= 2 vertical bar C-max and J2 vertical bar d(ij) = 1 vertical bar C-max (whereas other closely related versions such as J2 vertical bar n(j)<= 3 vertical bar C-max, J2 vertical bar d(ij) is an element of {1,2}C-max, J3 vertical bar d(ij) =1 vertical bar C-max, J3 vertical bar d(ij) =1 vertical bar and J vertical bar d(ij) =1, n(j) <= 3 vertical bar C-max are all known to be NP-complete). For the general case L > 2 (i.e., for the job-shop problem J vertical bar d(ij) =1, nj = L >2 vertical bar C-max) we present a competitive heuristic and provide experimental comparisons with other heuristic versions and, when possible, with the ideal integer linear programming formulation.

关键词： Job-shop scheduling mutual exclusion critical resources parallel programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Two disjoint shortest paths problem with non-negative edge length

引用

OPERATIONS RESEARCH LETTERS 2019年第1期47卷 66-69页

作者： Kobayashi, Yusuke Sako, Ryo Kyoto Univ Kyoto Japan Univ Tsukuba Tsukuba Ibaraki Japan

In the two disjoint shortest paths problem (2-DSPP), the input is a graph (or a digraph) and its vertex pairs (s(1), t(1)) and (S-2, t(2)), and the objective is to find two vertex-disjoint paths P-1 and P-2 such that P-i is a shortest path from s(i) to t(i) for i = 1, 2, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Disjoint paths Shortest path polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Splitting quaternion algebras over quadratic number fields

引用

JOURNAL OF SYMBOLIC COMPUTATION 2019年 94卷 173-182页

作者： Kutas, Peter Hungarian Acad Sci Inst Comp Sci & Control Budapest Hungary

We propose an algorithm for finding zero divisors in quaternion algebras over quadratic number fields, or equivalently, solving homogeneous quadratic equations in three variables over Q(root d) where d is a square-free integer. The algorithm is randomized and runs in polynomial time if one is allowed to call oracles for factoring integers. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Explicit isomorphism Full matrix algebra Quadratic form Quaternion algebra Quadratic number field polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：