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

linear time algorithm for the vertex-edge domination problem in convex bipartite graphs

DISCRETE OPTIMIZATION 2025年 55卷

作者： Buyukcolak, Yasemin Gebze Tech Univ Dept Math Kocaeli Turkiye

Given a graph G = ( V , E ) , a vertex u E V ve-dominates all edges incident to any vertex in the closed neighborhood N[u]. A subset D c V is a vertex-edge dominating set if, for each edge e E E , there exists a vertex u E D such that u ve-dominates e . The objective of the ve-domination problem is to find a minimum cardinality ve-dominating set in G . In this paper, we present a linear time algorithm to find a minimum cardinality ve-dominating set for convex bipartite graphs, which is a superclass of bipartite permutation graphs and a subclass of bipartite graphs, where the ve-domination problem is solvable in linear time and NP-complete, respectively. We also establish the relationship y ve = i v e for convex bipartite graphs. Our approach leverages a chain decomposition of convex bipartite graphs, allowing for efficient identification of minimum ve-dominating sets and extending algorithmic insights into ve-domination for specific structured graph classes.

关键词： Vertex-edge domination Independent vertex-edge domination linear time algorithm Convex bipartite graphs Chain decomposition

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for the Optimal Discrete IRS Beamforming

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2023年第3期12卷 496-500页

作者： Ren, Shuyi Shen, Kaiming Li, Xin Chen, Xin Luo, Zhi-Quan Chinese Univ Hong Kong Shenzhen Sch Sci & Engn Shenzhen 518172 Peoples R China Huawei Technol Xian 710075 Peoples R China Shenzhen Res Inst Big Data Shenzhen 518172 Peoples R China Chinese Univ Hong Kong Shenzhen Shenzhen 518172 Peoples R China

It remains an open problem to find the optimal configuration of phase shifts under the discrete constraint for intelligent reflecting surface (IRS) in polynomial time. The above problem is widely believed to be difficult because it is not linked to any known combinatorial problems that can be solved efficiently. The branch-and-bound algorithms and the approximation algorithms constitute the best results in this area. Nevertheless, this letter shows that the global optimum can actually be reached in linear time on average in terms of the number of reflective elements (REs) of IRS. The main idea is to geometrically interpret the discrete beamforming problem as choosing the optimal point on the unit circle. Although the number of possible combinations of phase shifts grows exponentially with the number of REs, it turns out that there are only a linear number of circular arcs that possibly contain the optimal point. Furthermore, the proposed algorithm can be viewed as a novel approach to a special case of the discrete quadratic program (QP).

关键词： Array signal processing Signal to noise ratio Approximation algorithms Visualization Optimization Big Data Wireless communication Discrete beamforming for IRS RIS global optimum linear time algorithm discrete quadratic program

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for connected p-centdian problem on block graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 318-326页

作者： Kien Trung Nguyen Wen Chean Teh Nguyen Thanh Hung Huong Nguyen-Thu Can Tho Univ Teacher Coll Math Dept Can Tho Vietnam Univ Sains Malaysia Sch Math Sci George Town 11800 Malaysia

We study the problem of finding a set of p connected vertices in a block graph to minimize the convex combination of the median and the center objective functions. This problem is called the connected p-centdian problem on block graphs. In the scope of this paper, we always focus on unweighted block graphs. For block graphs with two different edge lengths, the problem is NP-complete. For block graphs with uniform edge lengths, we focus on a special case of the connected p-centdian problem, namely where the median and the center functions receive equal weight. Concerning this specific problem, we consider a lexicographic order based on certain labels of the vertices and prove that there exists a connected p-centdian that contains a predetermined 1-centdian on the underlying graph. Applying this result, we develop a linear time algorithm for the problem. Finally, the problem under the general convex combination of the median and the center functions is also discussed. (c) 2022 Elsevier B.V. All rights reserved.

关键词： linear time algorithm Location problem Centdian problem Connected facilities Block graphs

来源：评论

学校读者我要写书评

暂无评论

A simple linear time algorithm to solve the MIST problem on interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 930卷 77-85页

作者： Li, Peng Shang, Jianhui Shi, Yi Chongqing Univ Technol Coll Sci Chongqing 400054 Peoples R China Shanghai Jiao Tong Univ Sch Math Sci Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Bio x Inst Key Lab Genet Dev & Neuropsychiat Disorders Minist Educ 1954 Huashan Rd Shanghai 200030 Peoples R China

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs.(c) 2022 Elsevier B.V. All rights reserved.

关键词： linear time algorithm Maximum internal spanning tree Connected interval graphs Normal orderings

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for Influence Maximization in Large-Scale Social Networks 24th

A Linear Time Algorithm for Influence Maximization in Large-...

引用

24th International Conference on Neural Information Processing (ICONIP)

作者： Wu, Hongchun Shang, Jiaxing Zhou, Shangbo Feng, Yong Chongiqng Univ Coll Comp Sci Chongqing Peoples R China Chongqing Univ Key Lab Dependable Serv Comp Cyber Phys Soc Minist Educ Chongqing Peoples R China

ISBN: (纸本)9783319701394;9783319701387

Influence maximization is the problem of finding k seed nodes in a given network as information sources so that the influence cascade can be maximized. To solve this problem both efficiently and effectively, in this paper we propose LAIM: a linear time algorithm for influence maximization in large-scale social networks. Our LAIM algorithm consists of two parts: (1) influence computation;and (2) seed nodes selection. The first part approximates the influence of any node using its local influence, which can be efficiently computed with an iterative algorithm. The second part selects seed nodes in a greedy manner based on the results of the first part. We theoretically prove that the time and space complexities of our algorithm are proportional to the network size. Experimental results on six real-world datasets show that our approach significantly outperforms other state-of-the-art algorithms in terms of influence spread, running time and memory usage.

关键词： Influence maximization Social networks linear time algorithm Computational complexity Data mining

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for metric dimension of cactus block graphs

引用

THEORETICAL COMPUTER SCIENCE 2016年 630卷 43-62页

作者： Hoffmann, Stefan Elterman, Alina Wanke, Egon Univ Dusseldorf Inst Comp Sci D-40225 Dusseldorf Germany

An undirected graph G = (V, E) has metric dimension at most k if there is a vertex set U subset of V such that vertical bar U vertical bar <= k and for all u, v is an element of V, u not equal v, there is a vertex w is an element of U such that d(G)(w, u) not equal d(G)(w, v), where d(G)(u, v) is the distance (the length of a shortest path in an unweighted graph) between u and v. The metric dimension of G is the smallest integer k such that G has metric dimension at most k. A cactus block graph is an undirected graph whose biconnected components are either cycles or complete graphs. We present a linear time algorithm for computing the metric dimension of cactus block graphs. (C) 2016 Elsevier B.V. All rights reserved.

关键词： linear time algorithm Metric dimension Cactus block graphs Resolving set

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for the unbalanced Hitchcock transportation problem

引用

NETWORKS 2016年第2期67卷 170-182页

作者： Matsui, Tomomi Scheifele, Rudolf Tokyo Inst Technol Grad Sch Decis Sci & Technol Dept Social Engn Meguro Ku Tokyo 1528550 Japan Univ Bonn Res Inst Discrete Math Lennestr 2 D-53113 Bonn Germany

The Hitchcock transportation problem is a special case of the minimum cost flow problem where the graph is bipartite and capacities are infinite. If we let m denote the size of the larger and n the size of the smaller side of the bipartition, we call the Hitchcock transportation problem unbalanced if m is much larger than n. The unbalanced case arises in various applications, motivating the search for algorithms whose running time dependence on m is as small as possible. In this work, we give an algorithm with running time , which is the fastest known algorithm whose running time grows linearly in m. Moreover, we compare running times of algorithms for the Hitchcock transportation problem and the minimum cost flow problem and point out the fastest algorithms for particular relations of m and n, where m and n denote the number of edges and vertices in the context of the minimum cost flow problem. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(2), 170-182 2016

关键词： Hitchcock transportation problem minimum cost flow problem linear time algorithm recursive algorithm bipartite graph parallel edges

来源：评论

学校读者我要写书评

暂无评论

linear-time algorithm for Quantum 2SAT

引用

THEORY OF COMPUTING 2018年第1期14卷 1-27页

作者： Arad, Itai Santha, Miklos Sundaram, Aarthi Zhang, Shengyu Technion Israel Inst Technol Haifa Israel Univ Paris Diderot Rech Paris France Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Chinese Univ Hong Kong Hong Kong Hong Kong Peoples R China

A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the N P-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors pi(ij) on a system of n qubits, and the task is to decide whether the Hamiltonian H = Sigma pi(ij) has a 0-eigenvalue, or all eigenvalues are greater than 1/n(alpha) for some alpha = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity O(n(4)) in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and n is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time O(n + m), where m is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is O((n+m)M(n)), where M(n) denotes the complexity of multiplying two n-bit integers.

关键词： quantum satisfiability davis-putnam procedure linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for clique-coloring problem in circular-arc graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期33卷 147-155页

作者： Liang, Zuosong Shan, Erfang Zhang, Yuzhong Qufu Normal Univ Sch Management Rizhao 276800 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287-292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.

关键词： Clique-coloring Circular-arc graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for the Line Subgraph Problem in Halin Graphs

A Linear Time Algorithm for the Line Subgraph Problem in Hal...

引用

2016 International Conference on Applied Mathematics, Simulation and Modelling(AMSM2016)

作者： Dingjun Lou Jun Liang Guanpu Han School of Data and Computer Science Sun Yat-sen University

Given a graph G=(V,E) and a positive integer p≤|E|. The Line Subgraph Problem is: Is there a subset E'?E such that |E'|≥p and H=(V,E) is a line graph. In this paper, we design a linear time algorithm to solv... 详细信息

ISBN: (纸本)9781510833890

关键词： halin graph line graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：