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 verte...
详细信息
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 lineartime 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.
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 ...
详细信息
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.
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 probl...
详细信息
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.
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 ...
详细信息
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.
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. T...
详细信息
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 lineartime for distance hereditary graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
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 inter...
详细信息
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.
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 obj...
详细信息
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 timealgorithm 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.
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 diffic...
详细信息
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 lineartime 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).
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 p...
详细信息
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.
We present a deterministic lineartime and space algorithm for ordered partition of a set T of n integers into n(1/2) sets T-0 <= T-1 <= ... T-n1/2 (-) (1), where vertical bar T-i vertical bar = theta(n(1/2)) an...
详细信息
ISBN:
(纸本)9783319196473;9783319196466
We present a deterministic lineartime and space algorithm for ordered partition of a set T of n integers into n(1/2) sets T-0 <= T-1 <= ... T-n1/2 (-) (1), where vertical bar T-i vertical bar = theta(n(1/2)) and T-i <= Ti+1 means that max T-i <= min Ti+1.
暂无评论