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

Coloring the square of a K₄-minor free graph

DISCRETE MATHEMATICS 2003年第1-3期269卷 303-309页

作者： Lih, KW Wang, WF Zhu, XD Acad Sinica Inst Math Taipei 115 Taiwan Zhejiang Normal Univ Dept Math Jinhua 321004 Zhejiang Peoples R China Natl Sun Yat Sen Univ Dept Appl Math Kaohsiung 804 Taiwan

Let G be a K-4-minor free graph with maximum degree Delta. We prove that the chromatic number of the square of G is at most (i) Delta + 3 if 2 less than or equal to Delta less than or equal to 3;or (ii) [3Delta/2] + 1 if Delta greater than or equal to 4. Examples are given to show the bounds can be attained. (C) 2003 Elsevier B.V. All rights reserved.

关键词： series-parallel graph K-4-minor free graph square chromatic number

来源：评论

学校读者我要写书评

暂无评论

A secure multisignature scheme with signing order verifiability

A secure multisignature scheme with signing order verifiabil...

引用

Symposium on Crytography and Information Security

作者： Tada, M Chiba Univ Inst Media & Informat Technol Chiba 2638522 Japan

In an order-specified multisignature scheme, one can verify not only a set of signers who have signed the message but also its signing order. Though we have seen several schemes with such properties proposed, none of them is given the security proof against active adversaries. The scheme [11] can be easily modified to be an order-specified multisignature scheme, but still has the restriction that the possible signing orders are only ones of the type of serial signing. In this paper, we propose the first order-specified multisignature scheme, which is shown to be secure against adaptive chosen-message insider attacks in the random oracle model [1], and which allows the signing orders to form like any series-parallel graphs. The security is shown by using ID-reduction technique, which reduces the security of multisignature schemes to those of multi-round identification schemes. Furthermore, we discuss the efficiency of the proposed scheme and the upper bound of the possible number of participating signers.

关键词： multisignature scheme signing order order-specified multisignature scheme series-parallel graph security

来源：评论

学校读者我要写书评

暂无评论

The circular chromatic number of series-parallel graphs of large odd girth

引用

DISCRETE MATHEMATICS 2002年第1-3期245卷 235-246页

作者： Pan, ZS Zhu, XD Natl Sun Yat Sen Univ Dept Appl Math Kaohsiung 80424 Taiwan

Suppose G is a series-parallel graph, We prove that if G has odd girth at least 6k - 1 then chi(c)(G) less than or equal to 8k/(4k - 1);if G has odd girth at least 6k + 1 then chi(c)(G) less than or equal to (4k + 1)/2k;if G has odd girth at least 6k + 3 then chi(c)(G) less than or equal to (4k + 3)/(2k + 1). (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： circular chromatic number circular flow number series-parallel graph odd girth

来源：评论

学校读者我要写书评

暂无评论

On the flow cost lowering problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2002年第2期137卷 265-271页

作者： Demgensky, I Noltemeier, H Wirth, HC Univ Wurzburg Dept Comp Sci D-97074 Wurzburg Germany

This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost, on each arc by upgrading the are. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series-parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series-parallel graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： minimum cost flow budget constrained upgrade problem series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Steiner trees and polyhedra

引用

DISCRETE APPLIED MATHEMATICS 2001年第1-3期112卷 101-120页

作者： Biha, MD Kerivin, H Mahjoub, AR Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Montreal PQ H3C 3A7 Canada Univ Clermont Ferrand CNRS Lab Limos F-63177 Clermont Ferrand France

In this paper we study the dominant of the Steiner tree polytope. We introduce a new class of valid inequalities that generalizes the so-called odd hole, wheel, bipartite, anti-hole and Steiner partition inequalities introduced by Chopra and Rao (Math. Programming 64 (1994) 209-229, 231-246), and we give sufficient conditions for these inequalities to define facets. We describe some procedures that permit to construct facets from known ones for the dominant of the Steiner tree polytope and the closely related Steiner connected subgraph polytope. Using these methods we give a counterexample to a conjecture of Chopra and Rao on the dominant of the Steiner tree polytope on 2-trees. We also describe the dominant of the Steiner tree polytope and the Steiner connected subgraph polytope on special classes of graphs. In particular, we show that if the underlying graph is series-parallel and the terminals satisfy certain conditions, then both polyhedra are given by the trivial inequalities and the Steiner partition inequalities. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： Steiner tree Steiner connected subgraph polytope facet series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Complexity of finding a join of maximum weight

引用

DISCRETE APPLIED MATHEMATICS 2001年第1-3期114卷 3-7页

作者： Ageev, AA Sobolev Inst Math Novosibirsk 630090 Russia

A subset of edges J subset of or equal to E(G) in a undirected graph G is called a join if at most half the edges of each cycle of G are contained in J. In this paper we consider the problem of finding a join of maximum weight: given a graph G and an edge weighting c:E(G) --> R, find a join of maximum weight. We show that the problem is NP-hard even in the case of 0, 1-weights, which answers a question of A. Frank in the negative. We also show that in the case of series-parallel graphs and arbitrary weights, the problem can be solved in time 0(n(3)), where n is the number of vertices in G. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： graph join NP-hard problem series-parallel graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the chromatic roots of generalized theta graphs

引用

JOURNAL OF COMBINATORIAL THEORY series B 2001年第2期83卷 272-297页

作者： Brown, JI Hickman, C Sokal, AD Wagner, DG Dalhousie Univ Dept Math & Stat Halifax NS B3H 3J5 Canada NYU Dept Phys New York NY 10003 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

The generalized theta graph Theta (S1,....Sk) consists of a pair of endvertices joined by k internally disjoint paths of lengths s(1),..., s(k) greater than or equal to 1. We prove that the roots of the chromatic polynomial pi(Theta (S1,...,Sk), z) of a k-ary generalized theta graph all lie in the disc \z- 1 \ less than or equal to [1 +o(1)] k/log k, uniformly in the path lengths s(1). Moreover, we prove that Theta (2,...,2) similar or equal to K-2,K-k indeed has a chromatic root of modulus [1 + o(1)] k/log k. Finally, for k less than or equal to 8 we prove that the generalized theta graph with a chromatic root that maximizes \ z - 1 \ is the one with all path lengths equal to 2;we conjecture that this holds for all k. (C) 2001 Academic Press.

关键词： graph generalized theta graph complete bipartite graph series-parallel graph chromatic polynomial chromatic roots Lambert W function Potts model

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期209卷 331-345页

作者： Colbourn, CJ Xue, GL Univ Vermont Dept Comp Sci & Elect Engn Burlington VT 05405 USA

Given a network with n vertices and m edges where each edge has an independent operational probability, we are interested in finding a vertex of the network whose expected number of reachable vertices is maximum. Such a vertex is called a most reliable sourer of the network. This problem was studied by Melachrinoudis and Helander (1996) where an O(n(2)) time algorithm was proposed when the given network is a tree. In a more recent paper, Xue presented an O(n) time algorithm for this problem when the given network is a tree, in this paper, we present an O(n) time algorithm for computing the most reliable source on series-parallel graphs, using their embeddings in 2-trees. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： algorithms time complexity partial 2-trees series-parallel graph network reliability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Steiner k-edge connected subgraph polyhedra

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2000年第1期4卷 131-144页

作者： Biha, MD Mahjoub, AR Ecole Polytech Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Univ Clermont Ferrand 2 LIMOS F-63177 Clermont Ferrand France

In this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Baiou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505-514, 1997 for the case k = 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are *** this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Baiou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505-514, 1997 for the case k = 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are allowed.

关键词： k-edge connected subgraph polytope series-parallel graph cut facet

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：