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

On the Konig deficiency of zero-reducible graphs

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期39卷 273-292页

作者： Bartha, Miklos Kresz, Miklos Mem Univ Newfoundland Dept Comp Sci St John NF A1B 3X5 Canada Univ Szeged Juhasz Gyula Fac Educ Boldogasszony Sgt 6 H-6725 Szeged Hungary InnoRenew CoE Izola 6310 Slovenia Univ Primorska Koper 6000 Slovenia

A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The Konig property is investigated in the context of reduction by introducing the Konig deficiency of a graph G as the difference between the vertex covering number and the matching number of G. It is shown that the problem of finding the Konig deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the Konig deficiency of graphs G having a vertex v such that G-v has a unique perfect matching is studied in connection with reduction.

关键词： graph matching Independent set Konig property graph reduction graph algorithm

来源：评论

学校读者我要写书评

暂无评论

IPED2: Inheritance Path Based Pedigree Reconstruction algorithm for Complicated Pedigrees

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2017年第5期14卷 1094-1103页

作者： He, Dan Wang, Zhanyong Parida, Laxmi Eskin, Eleazar IBM Corp Thomas J Watson Res Yorktown Hts NY 10598 USA Univ Calif Los Angeles Los Angeles CA 90095 USA

Reconstruction of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. The problem is known to be NP-hard even for datasets known to only contain siblings. Some recent methods have been developed to accurately and efficiently reconstruct pedigrees. These methods, however, still consider relatively simple pedigrees, for example, they are not able to handle half-sibling situations where a pair of individuals only share one parent. In this work, we propose an efficient method, IPED2, based on our previous work, which specifically targets reconstruction of complicated pedigrees that include half-siblings. We note that the presence of half-siblings makes the reconstruction problem significantly more challenging which is why previous methods exclude the possibility of half-siblings. We proposed a novel model as well as an efficient graph algorithm and experiments show that our algorithm achieves relatively accurate reconstruction. To our knowledge, this is the first method that is able to handle pedigree reconstruction from genotype data when half-sibling exists in any generation of the pedigree.

关键词： Pedigree reconstruction half-sibling inheritance path dynamic programming graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Better 3-coloring algorithms: Excluding a triangle and a seven vertex path

引用

THEORETICAL COMPUTER SCIENCE 2021年 850卷 98-115页

作者： Bonomo-Braberman, Flavia Chudnovsky, Maria Goedgebeur, Jan Maceli, Peter Schaudt, Oliver Stein, Maya Zhong, Mingxian Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires DF Argentina Univ Buenos Aires CONICET Inst Invest Ciencias Comp ICC Buenos Aires DF Argentina Princeton Univ Princeton NJ 08544 USA Univ Ghent Ghent Belgium Univ Mons Mons Belgium Ithaca Coll Ithaca NY 14850 USA Univ Cologne Cologne Germany Univ Chile Santiago Chile CUNY Lehman Coll Bronx NY 10468 USA CUNY Grad Ctr Bronx NY 10468 USA

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1, 2, 3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(vertical bar V (G)vertical bar(5)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)), and if G is bipartite, it improves to O(vertical bar V (G)vertical bar(2)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {P-t, C-3}-free graphs if and only if t <= 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P-7, C-3}-free graphs. We furthermore determine other cases of t, l, and k such that the family of minimal obstructions to list k-coloring in {P-t, C-l}-free graphs is finite. (C) 2020 Elsevier B.V. All rights reserved.

关键词： graph algorithm graph coloring Certifying algorithm Forbidden induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for the matched-domination problem in cographs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2011年第10期88卷 2042-2056页

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

Let G = (V, E) be a graph without isolated vertices. A matching in G is a set of independent edges in G. A perfect matching M in G is a matching such that every vertex of G is incident to an edge of M. A set S subset of V is a paired-dominating set of G if every vertex not in S is adjacent to a vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.

关键词： graph algorithm paired-domination constrained vertex set matched-domination cographs

来源：评论

学校读者我要写书评

暂无评论

Memory-aware framework for fast and scalable second-order random walk over billion-edge natural graphs

引用

VLDB JOURNAL 2021年第5期30卷 769-797页

作者： Shao, Yingxia Huang, Shiyue Li, Yawen Miao, Xupeng Cui, Bin Chen, Lei BUPT Sch Comp Sci Natl Pilot Software Engn Sch Beijing Peoples R China BUPT Beijing Key Lab Intelligent Telecommun Software & Beijing Peoples R China BUPT Sch Econ & Management Beijing Peoples R China Peking Univ Dept Comp Sci & Technol Beijing Peoples R China Peking Univ Key Lab High Confidence Software Technol MOE Beijing Peoples R China HKUST Dept Comp Sci & Engn Hong Kong Peoples R China

Second-order random walk is an important technique for graph analysis. Many applications including graph embedding, proximity measure and community detection use it to capture higher-order patterns in the graph, thus improving the model accuracy. However, the memory explosion problem of this technique hinders it from analyzing large graphs. When processing a billion-edge graph like Twitter, existing solutions (e.g., alias method) of the second-order random walk may take up 1796TB memory. Such high memory consumption comes from the memory-unaware strategies for the node sampling during the random walk. In this paper, to clearly compare the efficiency of various node sampling methods, we first design a cost model and propose two new node sampling methods: one follows the acceptance-rejection paradigm to achieve a better balance between memory and time cost, and the other is optimized for fast sampling the skewed probability distributions existed in natural graphs. Second, to achieve the high efficiency of the second-order random walk within arbitrary memory budgets, we propose a novel memory-aware framework on the basis of the cost model. The framework applies a cost-based optimizer to assign desirable node sampling method for each node or edge in the graph within a memory budget meanwhile minimizing the time cost of the random walk. Finally, the framework provides general programming interfaces for users to define new second-order random walk models easily. The empirical studies demonstrate that our memory-aware framework is robust with respect to memory and is able to achieve considerable efficiency by reducing 90% of the memory cost.

关键词： Random walk Memory efficient graph algorithm Large-scale

来源：评论

学校读者我要写书评

暂无评论

PARAMETERIZED COMPLEXITY OF ARC-WEIGHTED DIRECTED STEINER PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第2期25卷 583-599页

作者： Guo, Jiong Niedermeier, Rolf Suchy, Ondrej Univ Saarland D-66123 Saarbrucken Germany TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany Charles Univ Prague Dept Appl Math KAM CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic

We start a systematic parameterized computational complexity study of three NP-hard network design problems on arc-weighted directed graphs: directed Steiner tree, strongly connected Steiner subgraph, and directed Steiner network. We investigate their parameterized complexities with respect to the three parameterizations: "number of terminals," "an upper bound on the size of the connecting network," and the combination of these two. We achieve several parameterized hardness results as well as some fixed-parameter tractability results, in this way extending previous results of Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543-561].

关键词： computational intractability W[1]-hardness W[2]-hardness fixed-parameter tractability problem kernel graph algorithm network design

来源：评论

学校读者我要写书评

暂无评论

Complexity of the packing coloring problem for trees

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 771-778页

作者： Fiala, Jiri Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete. We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs. We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Packing coloring Computational complexity graph algorithm Chordal graph

来源：评论

学校读者我要写书评

暂无评论

Escaping a grid by edge-disjoint paths

引用

algorithmICA 2003年第4期36卷 343-359页

作者： Chan, WT Chin, FYL Ting, HF Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China

We study the edge-disjoint escape problem in grids. Given a set of n sources in a two-dimensional grid, the problem is to connect all sources to the grid boundary using a set of n edge-disjoint paths. Different from the conventional approach, which reduces the problem to a network flow problem, we solve the problem by first ensuring that no rectangle in the grid contain more sources than outlets, a necessary and. sufficient condition for the existence of a solution. Based on this condition, we give a greedy algorithm that finds the paths in O(n(2)) time, which is faster than all previous approaches. This problem finds applications in point-to-point delivery, VLSI reconfiguration, and package routing.

关键词： graph algorithm design and analysis of algorithm

来源：评论

学校读者我要写书评

暂无评论

A simplified algorithm computing all s-t bridges and articulation points

引用

DISCRETE APPLIED MATHEMATICS 2021年 305卷 103-108页

作者： Cairo, Massimo Khan, Shahbaz Rizzi, Romeo Schmidt, Sebastian Tomescu, Alexandru, I Zirondelli, Elia C. Univ Helsinki Dept Comp Sci Helsinki Finland Univ Verona Dept Comp Sci Verona Italy Univ Trento Dept Math Trento Italy

Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G. Similarly, an s-t articulation point of G is a node whose removal breaks all s-t paths of G. Computing the sequence of all s-t bridges of G (as well as the s-t articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm (Ford and Fulkerson, 1956). We show a simplified and self-contained algorithm computing all s-t bridges and s-t articulation points of G, based on a single graph traversal from s to t avoiding an arbitrary s-t path, which is interrupted at the s-t bridges. Its proof of correctness uses simple inductive arguments, making the problem an application of merely graph traversal, rather than of the more complex maximum flow problem. (C) 2021 The Author(s). Published by Elsevier B.V.

关键词： Reachability graph algorithm Strong bridge Strong articulation point Directed graph

来源：评论

学校读者我要写书评

暂无评论

Kernelization and Complexity Results for Connectivity Augmentation Problems

引用

NETWORKS 2010年第2期56卷 131-142页

作者： Guo, Jiong Uhlmann, Johannes Univ Jena Inst Informat D-07743 Jena Germany

Connectivity augmentation problems ask for adding a set of at most k edges (called links) whose insertion makes a given graph satisfy a specified connectivity property, such as bridge-connectivity or biconnectivity. A bridge-connected (biconnected) graph is a connected graph that does not possess an edge (a vertex) whose removal results in a disconnected graph. We show that, for bridge-connectivity and biconnectivity, the respective connectivity augmentation problems admit problem kernels with 0(0) vertices and links. Moreover, we study partial connectivity augmentation problems, naturally generalizing connectivity augmentation problems. Here, we do not require that, after adding the edges, the entire graph should satisfy the connectivity property, but a large subgraph. In this setting, three polynomial-time solvable connectivity augmentation problems behave differently, namely, the partial bridge-connectivity augmentation problem and the partial biconnectivity augmentation problem remain polynomial-time solvable, whereas the partial strong connectivity augmentation problem becomes W[2]-hard with respect to k. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 56(2), 131-142 2010

关键词： Combinatorial problem NP-complete problem graph algorithm fixed-parameter (in)tractability data reduction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：