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

THEORETICAL COMPUTER SCIENCE 2024年 1010卷

作者： Bang-Jensen, J. Bessy, S. Picasarri-Arrieta, L. Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Montpellier LIRMM CNRS Montpellier France Univ Cote Azur CNRS I3S Inria Sophia Antipolis France

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x(uv) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D. s, t, c) has a maximum flow x such that the maximum out-degree of the support D-x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p-path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a-path-flow x whose value is at least 2/3 of the value of a optimum p-path-flow when p is an element of{2, 3}, and at least 1/2 when p >= 4. When p = 2, they show that this is best possible unless P=NP. We show for each p >= 2 that the value of a maximum p-path-flow cannot be approximated by any ratio larger than 9/11, unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1/H(p) of the optimum solution, where H(p) is the p'th harmonic number (H(p) similar to ln(p)). We show that in the case where the network is acyclic, we can find such a maximum p-path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible.

关键词： Flows (Arc-)disjoint paths with prescribed end vertices Acyclic digraph Polynomial time algorithm NP-complete problem approximation algorithm Parameterised complexity

来源：评论

学校读者我要写书评

暂无评论

PARTITIONING A POLYGONAL REGION INTO TRAPEZOIDS

引用

JOURNAL OF THE ACM 1986年第2期33卷 290-312页

作者： ASANO, T ASANO, T IMAI, H UNIV TOKYO FAC ENGNDEPT MATH ENGN & INSTRUMENTAT PHYSBUNKYO KUTOKYO 113JAPAN OSAKA ELECTROCOMMUN UNIV FAC ENGNNEYAGAWAOSAKA 572JAPAN

The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number M* of the trapezoids in the minimum partition of a polygonal region P is shown to be M* = n + w - h - d - 1, where n, w, and h are the number of vertices, windows (holes), and horizontal edges of P, respectively, and d is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with P. Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an O(n2)-time algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an O(n log n)-time approximation algorithm with the performance bound 3 is presented.

关键词： approximation algorithm circle graph computational complexity computational geometry independent set intersection graph NP-complete straight-lines-in-the-plane graph VLSI design

来源：评论

学校读者我要写书评

暂无评论

On dominating set of some subclasses of string graphs

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2022年 107卷

作者： Chakraborty, Dibyayan Das, Sandip Mukherjee, Joydeep Indraprastha Inst Informat Technol Delhi India Indian Stat Inst Kolkata India Ramakrishna Mission Vivekananda Educ & Res Inst Belur West Bengal India

We provide constant factor approximation algorithms for the MINIMUM DOMINATING SET (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k & GE;0, unit B-k-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. We give an 18-approximation algorithm for the MDS problem on unit B-0-VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k(4))-approximation algorithm for the MDS problem on unit B-k-VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L-graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Dominating set approximation algorithm Geometric intersection graph String graph

来源：评论

学校读者我要写书评

暂无评论

Efficient connectivity analysis in underwater wireless sensor networks: a polynomial-time solution for the connectivity between nodes

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2024年第4期46卷 205-217页

作者： Altherwy, Youssef N. Prince Sattam bin Abdulaziz Univ Coll Comp Engn & Sci Dept Informat Syst Alkharj 11942 Saudi Arabia

Underwater wireless sensor networks (UWSNs) are a focus of research due to challenges in the unpredictable underwater environment. This study delves into connectivity among sensor nodes, particularly the likelihood of communication between nodes adrift with water currents, termed the two nodes connectivity (2Nodes connectivity) problem. Highlighting the computational complexity (2Nodes connectivity is #P-hard), we propose an innovative polynomial-time approximation algorithm, namely the 2Nodes connectivity algorithm. The algorithm yields precise connectivity outcomes for graphs composed of node-disjoint paths and serves as a lower bound solution for graphs where node-disjoint paths can be extracted. Through simulations in realistic UWSN scenarios, our algorithm demonstrates remarkable efficiency, making it an optimal choice for time-sensitive UWSN applications. Our research contributes both theoretical understanding and a practical algorithmic solution, addressing critical communication challenges in UWSNs.

关键词： underwater wireless sensor network UWSN connectivity approximation algorithm node-disjoint paths

来源：评论

学校读者我要写书评

暂无评论

Approximate separable multichoice optimization over monotone systems

引用

DISCRETE OPTIMIZATION 2022年第Part1期44卷

作者： Koutecky, Martin Levin, Asaf Meesum, Syed M. Onn, Shmuel Charles Univ Prague Prague Czech Republic Technion Israel Inst Technol Haifa Israel HBNI Inst Math Sci Chennai Tamil Nadu India

With each separable optimization problem over a given set of vectors is associated its multichoice counterpart which involves choosing n rather than one solutions from the set so as to maximize the given separable function over the sum of the chosen solutions. Such problems have been studied in various contexts under various names, such as load balancing in machine scheduling, congestion routing, minimum shared and vulnerable edge problems, and shifted optimization. Separable multichoice optimization has a very broad expressive power and can be hard already for explicitly given sets of binary points. In this article we consider the problem over monotone systems, also called independence systems. Typically such a system has exponential size, and we assume that it is presented implicitly by a linear optimization oracle. Our main results for separable multichoice optimization are the following. First, the problem over any monotone system with any separable concave function can be approximated in polynomial time with a constant approximation ratio which is independent of n. Second, the problem over any monotone system with an arbitrary separable function can be approximated in polynomial time with an approximation ratio of 1/(O(log n)). (C) 2021 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Load balancing Congestion routing Independence system Matching approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Rumor Blocking through Online Link Deletion on Social Networks

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2019年第2期13卷 16-16页

作者： Yan, Ruidong Li, Yi Wu, Weili Li, Deying Wang, Yongcai Renmin Univ China 59 Zhongguancun St Beijing 100872 Peoples R China Univ Texas Dallas 800 W Campbell Rd Richardson TX 75080 USA

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.

关键词： Social network rumor blocking approximation algorithm non-submodularity

来源：评论

学校读者我要写书评

暂无评论

Approximating bandwidth by mixing layouts of interval graphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2002年第4期15卷 435-449页

作者： Kratsch, D Stewart, L Univ Jena Fak Math & Informat D-07740 Jena Germany Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient approximation algorithms which are based on exact or approximate bandwidth layouts of related interval graphs. Specifically, we obtain a bandwidth approximation algorithm for circular-arc graphs that executes in O(n log(2) n) time and has performance ratio 2, which is the best possible performance ratio of any polynomial time bandwidth approximation algorithm for circular-arc graphs. For chordal graphs with at most k leaves in the clique tree, we obtain a performance ratio of 2k in O(k(n+m)) time, and our algorithm for k-polygon graphs has performance ratio 2k(2) and runs in time O(n(3)).

关键词： interval graphs circular-arc graphs chordal graphs polygon graphs bandwidth problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Robust Parameterized Submodular Function Maximization in Large-Scales

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2019年第4期36卷 1950022.1-1950022.24页

作者： Yang, Ruiqi Xu, Dachuan Jiang, Yanjun Wang, Yishui Zhang, Dongmei Beijing Univ Technol Dept Operat Res & Sci Comp 100 Pingleyuan Beijing 100124 Peoples R China Ludong Univ Sch Math & Stat Sci 186 Hongqi Middle Rd Yantai 264025 Shandong Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

We study a robust parameterized submodular function maximization inspired by [Mitrovic, S, I Bogunovic, A Norouzi-Fardand Jakub Tarnawski (2017). Streaming robust submodular maximization: A partitioned thresholding approach. In Proc. NIPS, pp. 4560-4569] and [Bogunovic, I, J Zhao and V Cevher (2018). Robust maximization of nonsubmodular objectives. In Proc. AISTATS, pp. 890-899]. In our setting, given a parameterized set function, there are two additional twists. One is that elements arrive in a streaming style, and the other is that there are at most tau items deleted from the algorithm's memory when the stream is finished. The goal is to choose a robust set from the stream such that the robust ratio is maximized. We propose a two-phase algorithm for maximizing a normalized monotone robust parameterized submodular function with a cardinality constraint and show the robust ratio is close to a constant as k -> infinity. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem.

关键词： Submodular function robust stream approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Path Planning of Data Mules in Sensor Networks

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2011年第1期8卷 1-1页

作者： Sugihara, Ryo Gupta, Rajesh K. Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

We study the problem of planning the motion of "data mules" for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules significantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: finding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the benefit from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the offline plan using online knowledge at runtime. Simulation experiments on Matlab and ns2 demonstrate that our offline and semionline algorithms produce significantly shorter path lengths and data delivery latency compared to previously proposed methods, suggesting that controlled mobility can be exploited much more effectively.

关键词： algorithms Design Performance Controlled mobility approximation algorithm integer programming semionline algorithm simulation

来源：评论

学校读者我要写书评

暂无评论

Bottleneck Crosstalk Minimization in Two- and Three-Layer Manhattan Channel Routing

引用

IEEE ACCESS 2024年 12卷 148332-148373页

作者： Mandal, Tarak Nath Sarkar, Suvarthi Roy, Deborupa Khan, Abhinandan Mehera, Ranjan Datta, Alak Kumar Pal, Rajat Kumar Microsoft India R&D Pvt Ltd Microsoft Campus Hyderabad 500032 Telangana India Univ Calcutta Dept Comp Sci & Engn Kolkata 700106 India Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 Assam India Oracle India Pvt Ltd Hyderabad 500081 India ARP Engn Kolkata 700056 India Anodot Inc Ashburn VA 20147 USA Visva Bharati Univ Dept Comp & Syst Sci Birbhum 731235 West Bengal India

VLSI physical design is a domain of work as old as more than five decades. Even then, as technology progresses, there are several challenging issues from the perspective of theoretical computer science as well as the high-performance requirements of the chip to be designed. Crosstalk is a threat to achieving routing solutions in high-performance VLSI circuits. As fabrication technology advances, closeness occurs among the devices and their interconnecting wires, the size of the devices and chips reduces, and circuits' operational frequencies increase. These result in crosstalk, a kind of electrical hazard, which over stresses wire segments that are placed sideways. In this paper, it has been proved that the bottleneck crosstalk minimisation problems in the reserved two- and three-layer Manhattan channel routing are NP-complete. It has also been established that the hardness proclaims in approximating all allied crosstalk minimisation problems. As a natural consequence, heuristics have been devised to realise two- and three-layer bottleneck crosstalk routing solutions for different predefined bottleneck values employed over already computed channel routing solutions. Exhaustive experimentation has been performed and promising experimental results have been accomplished often sacrificing a bit more channel area.

关键词： Routing Crosstalk Wires Minimization Very large scale integration Insulation life Delays Degradation Physical design Integrated circuit interconnections approximation algorithm bottleneck crosstalk channel routing problem crosstalk minimization heuristic high-performance routing NP-hardness two- and three-layer routing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：