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

9th Workshop on Algorithm Engineering and Experiments/4th Workshop on Analytic Algorithmics and Combinatorics

作者： Bose, Prosenjit Dujmovic, Vida Krizanc, Danny Langerman, Stefan Morin, Pat Wood, David R. Wuhrer, Stefanie Carleton Univ Sch Comp Sci Ottawa ON Canada Wesleyan Univ Dept Math & Comp Sci Middletown CT USA Univ Libre Bruxelles Dept Informat Brussels Belgium Univ Politecn Cataluna Dept Matemat Aplicada 2 Barcelona Spain

A graph G is a 2-tree if G = K-3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a lin... 详细信息

ISBN: (纸本)9780898716283

关键词： degree sequence graphical degree sequence 2-tree k-tree series-parallel graph treewidth

来源：评论

学校读者我要写书评

暂无评论

A characterization of the degree sequences of 2-trees

A characterization of the degree sequences of 2-trees

引用

21st Annual Symposium on Computational Geometry

作者： Bose, Prosenjit Dujmovic, Vida Krizanc, Danny Langerman, Stefan Morin, Pat Wood, David R. Wuhrer, Stefanie Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Wesleyan Univ Dept Math & Comp Sci Middletown CT USA Univ Libre Bruxelles Dept Informat FNRS Brussels Belgium Univ Politecn Cataluna Dept Matemat Aplicada 2 Barcelona Spain

A graph G is a 2-tree if G = K-3, or G has a vertex v of degree 2, whose neighbors are adjacent, and G \ v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a li... 详细信息

关键词： degree sequence graphical degree sequence 2-tree k-tree series-parallel graph treewidth

来源：评论

学校读者我要写书评

暂无评论

The Tutte polynomial characterizes simple outerplanar graphs

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 639-644页

作者： Goodall, Andrew J. de Mier, Anna Noble, Steven D. Noy, Marc Department of Applied Mathematics Institute of Theoretical Computer Science Charles University Prague Czech Republic Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain Department of Mathematical Sciences Brunel University Uxbridge United Kingdom

We show that if G is a simple outerplanar graph and H is a graph with the same Tutte polynomial as G, then H is also outerplanar. Examples show that the condition of G being simple cannot be omitted. © 2011 Elsev... 详细信息

关键词： Outerplanar graph series-parallel graph Tutte polynomial

来源：评论

学校读者我要写书评

暂无评论

Estimation of Expressions’ Complexities for Two-Terminal Directed Acyclic graphs

引用

Electronic Notes in Discrete Mathematics 2017年 63卷 109-116页

作者： Korenblit, Mark Levit, Vadim E. Department of Computer Science Holon Institute of Technology Holon Israel Department of Computer Science Ariel University Ariel Israel

The paper investigates relationship between algebraic expressions and graphs. Our intention is to simplify graph expressions and eventually find their shortest representations. We prove the decomposition lemma which asserts that the shortest expression of a subgraph of a graph G is not larger than the shortest expression of G. Using this finding, we estimate an upper bound of a size of the shortest expression for any two-terminal directed acyclic graph. © 2017 Elsevier B.V.

关键词： algebraic expression complexity edge-labeled graph series-parallel graph Two-terminal directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

A structured ElGamal-type multisignature scheme 3rd

引用

3rd International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2000)

作者： Burmester, M Desmedt, Y Doi, H Mambo, M Okamoto, E Tada, M Yoshifuji, Y Univ London Royal Holloway & Bedford New Coll Informat Secur Grp Egham TW20 0EX Surrey England Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA Okayama Univ Fac Sci Dept Math Okayama 700 Japan Tohoku Univ Educ Ctr Informat Proc Sendai Miyagi 980 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 980 Japan Univ Wisconsin Ctr Cryptog Comp & Network Secur Milwaukee WI 53201 USA

ISBN: (纸本)3540669671

We propose a structured multisignature scheme which is based on a modified ElGamal signature scheme and analyze its security. The structure takes into account the order of the signers. With serial structures, different signing orders produce different multisignatures. In contrast, with parallel structures the multisignatures are independent of the signing order. Our structured multisignatures can deal with structures which are composed of serial and parallel signing orders. We give reductions for the security of the proposed scheme, and for the specified order of the signers in the serial and mixed cases.

关键词： multisignature structured multisignature group structure series-parallel graph ElGamal signature

来源：评论

学校读者我要写书评

暂无评论

On Algebraic Expressions of Directed Grid graphs

引用

Electronic Notes in Discrete Mathematics 2017年 60卷 39-46页

作者： Korenblit, Mark Department of Computer Science Holon Institute of Technology Holon Israel

The paper investigates relationship between algebraic expressions and labeled graphs. We consider directed grid graphs having m rows and n columns. Our intent is to simplify the expressions of these graphs. With that end in view, we describe two algorithms which generate expressions of polynomial sizes for directed grid graphs. © 2017 Elsevier B.V.

关键词： backtracking decomposition expression grid Labeled graph series-parallel graph two-terminal directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Enumeration of Labeled series-parallel Tricyclic graphs

引用

Journal of Mathematical Sciences (United States) 2023年第6期275卷 778-782页

作者： Voblyi, V.A. Russian Institute for Scientific and Technical Information Moscow Russian Federation

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. An explicit formula for the number of labeled series-parallel tricyclic graphs with a given number of vertices is obtained, and the corresponding asymptotics for the number of such graphs with a large number of vertices is found. We prove that under a uniform probability distribution, the probability that the labeled tricyclic graph is a series-parallel graph is asymptotically equal to 13/15. © 2023, Springer Nature Switzerland AG.

关键词： 05C30 asymptotics enumeration labeled graph probability series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

A computation method of LSN for extended 2-b-SPGs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2001年第11期E84A卷 2838-2851页

作者： Ge, QW Sugimoto, Y Yamaguchi Univ Fac Educ Yamaguchi 7538513 Japan NEC Software Chugoku Ltd Hiroshima 7320827 Japan

Topological sorting is, given with a directed acyclic graph G = (V, E), to find a total ordering of the vertices such that if (u, v) is an element of E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

关键词： topological sorting directed acyclic graph series-parallel graph legal sequence legal sequence number

来源：评论

学校读者我要写书评

暂无评论

Partitioning a multi-weighted graph to connected subgraphs of almost uniform size

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2007年第2期E90D卷 449-456页

作者： Ito, Takehiro Goto, Kazuya Zhou, Xiao Nishizeki, Takao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers l(i) and u(i), 1 <= i <= q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 <= i <= q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

关键词： algorithm choice partition lower bound maximum partition problem minimum partition problem multi-weighted graph partial k-tree series-parallel graph uniform partition upper bound

来源：评论

学校读者我要写书评

暂无评论

Circular Separation Dimension of a Subclass of Planar graphs

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2017年第3期19卷

作者： Bharathi, Arpitha P. De, Minati Lahiri, Abhiruk Indian Inst Sci Dept Comp Sci & Automat Bangalore Karnataka India

A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension of a graph G, denoted by pi degrees (G), is the minimum number of circular orderings of the vertices of G such that every pair of non-adjacent edges is separated in at least one of the circular orderings. This notion is introduced by Loeb and West in their recent paper. In this article, we consider two subclasses of planar graphs, namely 2-outerplanar graphs and series-parallel graphs. A 2-outerplanar graph has a planar embedding such that the subgraph obtained by removal of the vertices of the exterior face is outerplanar. We prove that if G is 2-outerplanar then pi degrees (G) = 2. We also prove that if G is a series-parallel graph then pi degrees (G) <= 2.

关键词： Circular separation dimension planar graph 2-outerplanar graph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：