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

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 MAXIMUM CAPACITY PATH PROBLEM

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1991年第3期53卷 402-404页

作者： PUNNEN, AP INDIAN INST TECHNOL DEPT MATHKANPUR 208016UTTAR PRADESHINDIA

The maximum capacity path problem is to find a path joining two fixed vertices of an edge weighted graph such that the minimum edge weight is maximized. The best known algorithm to solve this problem has a worst-case complexity of O(min{m + n log n, m log(n)W}), where m is the number of edges, n is the number of vertices and W is the maximum edge capacity. We give a simple O(m) algorithm to solve this problem. As a by-product of this result, we have an O(m2) algorithm for a bicriteria path problem which is an improvement over the available O(m2log n) algorithm.

关键词： NETWORKS SHORTEST PATHS MAXMIN PATHS linear time algorithm COMPUTATIONAL COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

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 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 minimum fill-in and treewidth for distance hereditary graphs

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期99卷 367-400页

作者： Broersma, HJ Dahlhaus, E Kloks, T Univ Twente Fac Math Sci NL-7500 AE Enschede Netherlands Univ Bonn Dept Comp Sci D-5300 Bonn Germany

A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. The MINIMUM FILL-IN problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The TREEWIDTH problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this paper we show that both problems are solvable in linear time for distance hereditary graphs. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： distance hereditary graphs MINIMUM FILL-IN TREEWIDTH chordal graphs linear time algorithm fragment tree tree representation

来源：评论

学校读者我要写书评

暂无评论

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 the induced disjoint paths problem in planar graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第2期78卷 670-680页

作者： Kawarabayashi, Ken-ichi Kobayashi, Yusuke Univ Tokyo Tokyo 1138656 Japan Natl Inst Informat Tokyo 1018430 Japan

In this paper, we consider a problem which we call the induced disjoint paths problem (IDPP) for planar graphs. We are given a planar graph G and a collection of vertex pairs {(s(1), t(1)), ... ,(s(k), t(k))}. The objective is to find k paths P-1, ..., P-k such that P-i is a path from s(i) to t(i) and P-i and P-j have neither common vertices nor adjacent vertices for any distinct i, j. This problem setting is a generalization of the disjoint paths problem, since if we subdivide each edge, then desired disjoint paths would be induced disjoint paths. The problem is motivated by not only the disjoint paths problem but also the recognition of an induced subgraph. The latter has been developed in recent years, and this is actually connected to the Strong Perfect Graph Theorem (Chudnovsky, et al., 2006) [1], and the recognition of the perfect graphs (Chudnovsky, et al., 2005) [2]. Our main result in this paper is to give a linear time algorithm for the IDPP for planar graphs. This generalizes the result by Reed, Robertson, Schrijver and Seymour (1993) [14]. This also gives a polynomial time algorithm to find an induced circuit through given k vertices in planar graphs if one exists when k is fixed. The case k = 2 was previously proved by McDiarmid. Reed, Schrijver and Shepherd (1994) [10]. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Disjoint paths Induced subgraph Planar graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2012年第1期14卷 147-158页

作者： Lonc, Zbigniew Naroski, Pawel Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v(0), epsilon(1), v(1), epsilon(2), v(2), ... , v(m-1), epsilon(m), v(m) of vertices and edges in H such that each edge of H appears in this sequence exactly once and v(i-1);v(i) is an element of epsilon(i), v(i-1) not equal v(i), for every i = 1, 2, ... , m. This concept is a natural extension of the graph theoretic notion of an Euler walk to the case of 3-uniform hypergraphs. We say that a 3-uniform hypergraph H is strongly connected if it has no isolated vertices and for each two edges e and f in H there is a sequence of edges starting with e and ending with f such that each two consecutive edges in this sequence have two vertices in common. In this paper we give an algorithm that constructs an Euler walk in a strongly connected 3-uniform hypergraph (it is known that such a walk in such a hypergraph always exists). The algorithm runs in time O(m), where m is the number of edges in the input hypergraph.

关键词： 3-uniform hypergraph Euler walk strongly connected hypergraph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：