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

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期38卷 646-665页

作者： Miyazaki, Shuichi Okamoto, Kazuya Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Hosp Div Med Informat Technol & Adm Planning Sakyo Ku 54 Kawaharacho Kyoto 6068507 Japan

In the stable marriage problem, we are given a set of men, a set of women, and each person's preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where k(2) sets of preference lists Li (1ik) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all Li. We show that the decision problem is NP-complete for the following two restricted cases;(1) k=2 and each person's preference list is of length at most four, and (2) k=4, each man's preference list is of length at most three, and each woman's preference list is of length at most four. On the other hand, we show that it is solvable in linear time for any k if each man's preference list is of length at most two (women's lists can be of unbounded length). We also show that if each woman's preference lists are same in all Li, then the problem can be solved in linear time.

关键词： Stable marriage problem Stable matching NP-completeness linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

Secure domination in proper interval graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 247卷 70-76页

作者： Araki, Toru Miyazaki, Hiroka Gunma Univ Grad Sch Sci & Technol Kiryu Gunma 3768515 Japan

A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u is not an element of S, there is a vertex v is an element of S such that uv is an edge and (S \ {v}) boolean OR {u} is also a dominating set of G. The secure domination number gamma(s)(G) is the cardinality of a smallest secure dominating set of G. In this paper, we propose a linear-time algorithm for finding the secure domination number of proper interval graphs. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Secure domination Domination Proper interval graphs linear time algorithm Powers of a path

来源：评论

学校读者我要写书评

暂无评论

On computing a minimum secure dominating set in block graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期35卷 613-631页

作者： Pradhan, D. Jha, Anupriya Indian Inst Technol Dept Appl Math Dhanbad Bihar India

In a graph , a set is said to be a dominating set of G if for every vertex , there exists a vertex such that . A secure dominating set of the graph G is a dominating set D of G such that for every , there exists a vertex such that and is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.

关键词： Domination Secure domination Block graphs linear time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Direct Superbubble Detection

引用

algorithmS 2019年第4期12卷 81-81页

作者： Gaertner, Fabian Stadler, Peter F. Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Augustuspl 12 D-04107 Leipzig Germany Univ Leipzig Bioinformat Grp Dept Comp Sci Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat German Ctr Integrat Biodivers Res iDiv Halle Jena D-04107 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github.

关键词： superbubble depth-first search cycles linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple linear time approximation algorithm for betweenness

引用

OPERATIONS RESEARCH LETTERS 2012年第6期40卷 450-452页

作者： Makarychev, Yury Toyota Technol Inst Chicago IL 60637 USA

We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form x similar to {y, z} requires that vertex x lies between vertices y and z. Our goal is to find a vertex ordering that maximizes the number of satisfied constraints. In 1995, Chor and Sudan designed an SDP algorithm that satisfies half of all constraints in a satisfiable instance. We present a simple combinatorial linear time algorithm with the same approximation guarantee. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Betweenness problem Approximation algorithm linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Superbubbles revisited

引用

algorithmS FOR MOLECULAR BIOLOGY 2018年第1期13卷 16-16页

作者： Gaertner, Fabian Mueller, Lydia Stadler, Peter F. Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Augustuspl 12 D-04107 Leipzig Germany Univ Leipzig Bioinformat Grp Dept Comp Sci Hartelstr 16 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Dept Comp Sci Nat Language Proc Grp Augustuspl 12 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Fraunhofer Inst Cell Therapy & Immunol Perlickstr 1 D-04103 Leipzig Germany Univ Vienna Dept Theoret Chem Wahringer Str 17 A-1090 Vienna Austria Ctr Noncoding RNA Technol & Hlth Gronegardsvej 3 DK-1870 Frederiksberg C Denmark Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Background: Superbubbles are distinctive subgraphs in direct graphs that play an important role in assembly algorithms for high- throughput sequencing ( HTS) data. Their practical importance derives from the fact they are connected to their host graph by a single entrance and a single exit vertex, thus allowing them to be handled independently. Efficient algorithms for the enumeration of superbubbles are therefore of important for the processing of HTS data. Superbubbles can be identified within the strongly connected components of the input digraph after transforming them into directed acyclic graphs. The algorithm by Sung et al. ( IEEE ACM Trans Comput Biol Bioinform 12: 770- 777, 2015) achieves this task in O( m log( m))- time. The extraction of superbubbles from the transformed components was later improved to by Brankovic et al. ( Theor Comput Sci 609: 374- 383, 2016) resulting in an overall O( m + n)- time algorithm. Results: A re- analysis of the mathematical structure of superbubbles showed that the construction of auxiliary DAGs from the strongly connected components in the work of Sung et al. missed some details that can lead to the reporting of false positive superbubbles. We propose an alternative, even simpler auxiliary graph that solved the problem and retains the linear running time for general digraph. Furthermore, we describe a simpler, space- efficient O( m + n) - time algorithm for detecting superbubbles in DAGs that uses only simple data structures. Implementation: We present a reference implementation of the algorithm that accepts many commonly used formats for the input graph and provides convenient access to the improved algorithm. https :// githu b. com/ Fabia nexe/ Super bubble

关键词： Superbubble de Bruijn graph Genome assembly linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Bipartite Grid Partitioning of a Random Geometric Graph 13

Bipartite Grid Partitioning of a Random Geometric Graph

引用

13th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS)

作者： Chen, Zizhen Matula, David W. Southern Methodist Univ Dept Comp Sci & Engn Dallas TX 75275 USA

ISBN: (纸本)9781538639917

We investigate the problem of efficient computation of a partition of a Random Geometric Graph (RGG) into a limited number of densely packed bipartite grid sub graphs. The study focuses on the collection of subgraphs each individually having similar size and structure and the union employing most (e.g. over 85%) of the vertices. The residual vertices we seek to minimize are attributed to the inherent variations in densities of the randomly placed vertices and to any shortcomings of our greedy algorithms. RGG's have been extensively employed in recent times to model the deployment of numerous instances of Wireless Sensor Networks (WSN's) Pl. The properties investigated in our selected bipartite grid backbones are those deemed most relevant for applications to the foundations of this widely growing field. Distributed algorithms are primarily used to determine backbones. Our results review what backbone grid partitions exist in the data. This provides a metric to measure the effectiveness of any distributed algorithm against an existing optimal result. The visual display of selected backbone grids suggests local algorithm design strategies. Furthermore, these partitions must be efficiently computable for highly scalable computation, e.g. WSN's with 100's of thousands of vertices and millions of edges in the resulting RGG. We consider distributions over a segment of the plane and over the surface of the sphere to model sensor distributions both in limited planar regions, all around the globe or on distant planets.

关键词： Random Geometric Graph Wireless Sensor Network Bipartite Subgraph Grid Partitioning linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Basic primal infon logic

引用

JOURNAL OF LOGIC AND COMPUTATION 2016年第1期26卷 117-141页

作者： Cotrini, Carlos Gurevich, Yuri Swiss Fed Inst Technol Zurich Switzerland Microsoft Res Bengaluru Karnataka India

Primal infon logic (PIL) was introduced in 2009 in the framework of policy and trust management. In the meantime, some generalizations appeared, and there have been some changes in the syntax of the basic PIL. This article is on the basic PIL, and one of our purposes is to 'institutionalize' the changes. We prove a small-model theorem for the propositional fragment of basic primal infon logic (PPIL), give a simple proof of the PPIL locality theorem and present a linear-time decision algorithm (announced earlier) for PPIL in a form convenient for generalizations. For the sake of completeness, we cover the universal fragment of basic PIL. We wish that this article becomes a standard reference on basic PIL.

关键词： Authorization language basic primal logic DKAL infon logic Kripke semantics linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：