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

The Power of linear-time Data Reduction for Maximum Matching

ALGORITHMICA 2020年第12期82卷 3521-3565页

作者： Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Univ Durham Dept Comp Sci Durham England TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m root n) time;however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

关键词： Maximum-cardinality matching Bipartite graphs linear-time algorithms Kernelization Parameterized complexity analysis FPT in P

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for four-partitioning four-connected planar graphs

引用

INFORMATION PROCESSING LETTERS 1997年第6期62卷 315-322页

作者： Nakano, S Rahman, MS Nishizeki, T TOHOKU UNIV GRAD SCH INFORMAT SCISENDAIMIYAGI 98077JAPAN

Given a graph G = (V,E), four distinct vertices u(1),u(2),u(3),u(4) is an element of V and four natural numbers n(1),n(2),n(3),n(4) such that Sigma(i=1)(4)n(i) = \V\, we wish to find a partition V-1,V-2,V-3,V-4 of the vertex set V such that u(i) is an element of V-i, \V-i\ = n(i) and V-i induces a connected subgraph of G for each i, 1 less than or equal to i less than or equal to 4. In this paper we give a simple linear-time algorithm to find such a partition if G is a 4-connected planar graph and u(1), u(2), u(3) and u(4) are located on the same face of a plane embedding of G. Our algorithm is based on a ''4-canonical decomposition'' of G, which is a generalization of an st-numbering and a ''canonical 4-ordering'' known in the area of graph drawings. (C) 1997 Elsevier Science B.V.

关键词： graph partition four-connected planar graph algorithms linear-time algorithms canonical decomposition st-numbering

来源：评论

学校读者我要写书评

暂无评论

linear-time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期50卷 721-738页

作者： Hung, Ruo-Wei Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan

A bipartite graph G=(U,W,E) with vertex set V=Ua(a)W is convex if there exists an ordering of the vertices of W such that for each uaU, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.

关键词： Graph algorithms linear-time algorithms Paired-domination Total domination Convex bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

Forest-like abstract Voronoi diagrams in linear time

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2018年 68卷 134-145页

作者： Bohler, Cecilia Klein, Rolf Lingas, Andrzej Liu, Chih-Hung Univ Bonn Inst Comp Sci 1 Bonn Germany Lund Univ Dept Comp Sci Lund Sweden

The Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V (S) is a tree, and for each subset S' subset of S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V (S) inside D can be constructed in linear time. (c) 2017 Elsevier B.V. All rights reserved.

关键词： Voronoi diagrams General distance Abstract Voronoi diagrams linear-time algorithms Forest structures

来源：评论

学校读者我要写书评

暂无评论

Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in linear time

引用

ALGORITHMICA 2023年第9期85卷 2605-2666页

作者： Didimo, Walter Kaufmann, Michael Liotta, Giuseppe Ortali, Giacomo Univ Perugia Dept Engn Perugia Italy Univ Tubingen Tubingen Germany

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take;the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.

关键词： Orthogonal drawings Bend minimization linear-time algorithms Plane graphs Series-parallel graphs

来源：评论

学校读者我要写书评

暂无评论

A linear time ALGORITHM FOR SMALLEST AUGMENTATION TO 3-EDGE-CONNECT A GRAPH

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1993年第4期E76A卷 518-531页

作者： WATANABE, T YAMAKADO, M Hiroshima Univ Higashi-Hiroshima-shi Japan

The subject of the paper is to propose an O(Absolute value of V + Absolute value of E) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by ''Given an undirected graph G0 = (V, E), find an edge set E' of minimum cardinality such that the graph (V,E or E') (denoted as G0 + E') is 3-edge-connected, where each edge of E' connects distinct vertices of V.'' Such a set E' is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0 + E' is required to be simple (G0 + E' may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k less-than-or-equal-to 3, and (2) determining a minimum set of edges whose addition to 66 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(Absolute value of V + Absolute value of E) algorithm that has already been existing. The paper proposes an 0 (Absolute value of V + Absolute value of E) algorithm for the subproblem (2). Combining these algorithms makes an O(Absolute value of V + Absolute value of E) algorithm for finding a solution to UW-3-ECA (M). Furthermore, it is shown that a solution E' to UW-3-ECA (M) is also a solution to UW-3-ECA(S) if Absolute value of V greater-than-or-equal-to 4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA (S).

关键词： linear-time algorithms 3-EDGE-CONNECTED GRAPHS CONNECTIVITY AUGMENTATION COMPUTATIONAL COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

A linear-time Algorithm for Broadcast Domination in a Tree

引用

NETWORKS 2009年第2期53卷 160-169页

作者： Dabney, John Dean, Brian C. Hedetniemi, Stephen T. Clemson Univ Sch Comp Clemson SC 29634 USA

The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating (broadcasting to) all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that Sigma(v is an element of v) f(v) is minimized, and such that every vertex u with f(u) = 0 Is within distance f(v) of some vertex v with f(v) > 0. The problem is solvable in polynomial time on a general graph (Heggernes and Lokshtanov, Disc Math (2006), 3267-3280) and Blair et al. (Congr. Num. (2004), 55-77.) gave an O(n(2)) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on "nonlocal" information from vertices far away from v, whereas almost all other linear-time algorithms for trees only make use of local information. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(2), 160-169 2009

关键词： broadcasts domination tree algorithms linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A SIMPLE linear-time ALGORITHM FOR COMPUTING THE CENTER OF AN INTERVAL GRAPH

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1990年第3-4期34卷 121-128页

作者： OLARIU, S Department of Computer Science Old Dominion University Norfolk VA 23529-0162 United States

The computational problem of finding the center of a graph is motivated by a number of facility-location problems. We exploit a new characterization of interval graphs for the purpose of obtaining a linear-time algori... 详细信息

关键词： Interval graphs diameter center linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A Simple linear-time Recognition Algorithm for Weakly Quasi-Threshold Graphs

引用

GRAPHS AND COMBINATORICS 2011年第4期27卷 557-565页

作者： Nikolopoulos, Stavros D. Papadopoulos, Charis Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of {P-4, co-(2P(3))}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional O(n) time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph.

关键词： Weakly quasi-threshold graphs Cographs Forbidden induced subgraphs Recognition linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

RECOGNIZING P4-SPARSE GRAPHS IN linear time

引用

SIAM JOURNAL ON COMPUTING 1992年第2期21卷 381-406页

作者： JAMISON, B OLARIU, S OLD DOMINION UNIV DEPT COMP SCI NORFOLK VA 23529 USA

A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. One remarkable feature of P4-sparse graphs is that they admit a tree representation unique up to isomorphism. It has been shown that this tree representation can be obtained in polynomial time. This paper gives a linear time algorithm to recognize P4-sparse graphs and shows how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation in linear time.

关键词： COGRAPHS P4-SPARSE GRAPHS linear-time algorithms OPTIMAL algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：