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

A Note on Algebraic Expressions of Rhomboidal Labeled graphs

Electronic Notes in Discrete Mathematics 2015年 48卷 243-250页

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

This paper investigates relationship between algebraic expressions and labeled graphs. We consider rhomboidal non-series-parallel graphs, specifically, a new digraph called a full square rhomboid. Our intent is to simplify the expressions of rhomboidal graphs and eventually find their shortest representations. With that end in view, we describe and compare two decomposition methods for generating expressions of labeled graphs. © 2015 Elsevier B.V.

关键词： Decomposition Expression Labeled graph Rhomboid series-parallel graph Two-terminal directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Excluding Braess's Paradox in Nonatomic Selfish Routing 8th

引用

8th International Symposium on Algorithmic Game Theory (SAGT)

作者： Chen, Xujin Diao, Zhuo Hu, Xiaodong Chinese Acad Sci Inst Appl Math AMSS Beijing 100190 Peoples R China

ISBN: (纸本)9783662484333;9783662484326

Braess's paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve overall network performance. Under the model of nonatomic selfish routing, we characterize the topologies of k-commodity undirected and directed networks in which Braess's paradox never occurs. Our results generalize Milchtaich's series-parallel characterization for the single-commodity undirected case.

关键词： Nonatomic selfish routing Braess's paradox Singlecommodity network Multicommodity network series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Finding Maximum Common Biconnected Subgraphs in series-parallel graphs

Finding Maximum Common Biconnected Subgraphs in Series-Paral...

引用

39th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Kriege, Nils Mutzel, Petra Tech Univ Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9783662444658;9783662444641

The complexity of the maximum common subgraph problem in partial k-trees is still largely unknown. We consider the restricted case, where the input graphs are k-connected partial k-trees and the common subgraph is required to be k-connected. For biconnected outerplanar graphs this problem is solved and the general problem was reported to be tractable by means of tree decomposition techniques. We discuss key obstacles of tree decompositions arising for common subgraph problems that were ignored by previous algorithms and do not occur in outerplanar graphs. We introduce the concept of potential separators, i.e., separators of a subgraph to be searched that not necessarily are separators of the input graph. We characterize these separators and propose a polynomial time solution for series-parallel graphs based on SP-trees.

关键词： Tree decomposition maximum common subgraph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

On the feedback vertex set polytope of a series-parallel graph

引用

DISCRETE OPTIMIZATION 2009年第3期6卷 271-287页

作者： Fiorini, Samuel Marcotte, Odile Univ Quebec Montreal PQ H3T 2A7 Canada HEC Montreal GERAD Montreal PQ H3T 2A7 Canada Univ Libre Bruxelles Dept Math B-1050 Brussels Belgium

The minimum weight feedback vertex set problem (FVS) on series-parallel graphs can be solved in O(n) time by dynamic programming. This solution, however, does not provide a "nice" certificate of optimality. We prove a min-max relation for FVS on series-parallel graphs with no induced subdivision of K-2,K-3 (a class of graphs containing the outerplanar graphs), thereby establishing the existence of nice certificates for these graphs. Our proof relies on the description of a complete set of inequalities defining the feedback vertex set polytope of a series-parallel graph with no induced subdivision of K-2,K-3. We also prove that many of the inequalities described are facets of this polytope. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Feedback vertex set Min-max relation series-parallel graph Polytope Facet

来源：评论

学校读者我要写书评

暂无评论

Spanning Distribution Trees of graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2014年第3期E97D卷 406-412页

作者： Kawabata, Masaki Nishizeki, Takao Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan

Let G be a graph with a single source w, assigned a positive integer called the supply. Every vertex other than w is a sink, assigned a nonnegative integer called the demand. Every edge is assigned a positive integer called the capacity. Then a spanning tree T of G is called a spanning distribution tree if the capacity constraint holds when, for every sink v, an amount of flow, equal to the demand of v, is sent from w to v along the path in T between them. The spanning distribution tree problem asks whether a given graph has a spanning distribution tree or not. In the paper, we first observe that the problem is NP-complete even for series-parallel graphs, and then give a pseudo-polynomial time algorithm to solve the problem for a given series-parallel graph G. The computation time is bounded by a polynomial in n and D, where n is the number of vertices in G and D is the sum of all demands in G.

关键词： spanning distribution tree series-parallel graph flow supply demand partial k-tree

来源：评论

学校读者我要写书评

暂无评论

Bandwidth consecutive multicolorings of graphs

引用

THEORETICAL COMPUTER SCIENCE 2014年 532卷 64-72页

作者： Nishikawa, Kazuhide Nishizeki, Takao Zhou, Xiao Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Let G be a simple graph in which each vertex v has a positive integer weight b(v) and each edge (v, w) has a nonnegative integer weight b(v, w). A bandwidth consecutive multicoloring of G assigns each vertex v a specified number b(v) of consecutive positive integers so that, for each edge (v, w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v, w). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given series-parallel graph with the minimum span. We finally extend the results to the case where a given graph G is a partial k-tree, that is, G has a bounded tree-width. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Bandwidth coloring Channel assignment Multicoloring series-parallel graph Partial k-tree Algorithm Acyclic orientation Approximation FPTAS

来源：评论

学校读者我要写书评

暂无评论

Generalized max flow in series-parallel graphs

引用

DISCRETE OPTIMIZATION 2013年第2期10卷 155-162页

作者： Krumke, Sven O. Zeck, Christiane Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany

In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(nm+m log m) time, where m is the number of arcs, and a dynamic programming algorithm with running time O(m log m). For the integral version of the problem, which is known to be N P-complete, we present a pseudo-polynomial algorithm. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Generalized flow Max flow problem series-parallel graph Integral flow

来源：评论

学校读者我要写书评

暂无评论

Spanning Distribution Forests of graphs (Extended Abstract)

Spanning Distribution Forests of Graphs (Extended Abstract)

引用

8th International Frontiers of Algorithmics Workshop (FAW)

作者： Inoue, Keisuke Nishizeki, Takao Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan

ISBN: (纸本)9783319080161;9783319080154

Assume that a graph G has l sources, each assigned a non-negative integer called a supply, that all the vertices other than the sources are sinks, each assigned a non-negative integer called a demand, and that each edge of G is assigned a non-negative integer, called a capacity. Then one wishes to find a spanning forest F of G such that F consists of l trees, each tree T in F contains a source w, and the flow through each edge of T does not exceed the edge-capacity when a flow of an amount equal to a demand is sent from w to each sink in T along the path in T. Such a forest F is called a spanning distribution forest of G. In the paper, we first present a pseudo-polynomial time algorithm to find a spanning distribution forest of a given series-parallel graph, and then extend the algorithm for graphs with bounded tree-width.

关键词： spanning distribution forest series-parallel graph network flow supply demand bounded tree-width

来源：评论

学校读者我要写书评

暂无评论

BOUNDING THE NUMBER OF REDUCED TREES, COgraphS, AND series-parallel graphS BY COMPRESSION

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2013年第2期5卷 1360001-1-1360001-14页

作者： Uno, Takeaki Uehara, Ryuhei Nakano, Shin-Ichi Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Gunma Univ Fac Engn Dept Comp Sci Gunma 3768515 Japan

We give an efficient encoding and decoding scheme for computing a compact representation of a graph in one of unordered reduced trees, cographs and series-parallel graphs. The unordered reduced trees are rooted trees in which (i) the ordering of children of each vertex does not matter, and (ii) no vertex has exactly one child. This is one of basic models frequently used in many areas. Our algorithm computes a bit string of length 2l - 1 for a given unordered reduced tree with l >= 1 leaves in O(l) time, whereas a known folklore algorithm computes a bit string of length 2n-2 for an ordered tree with n vertices. Note that in an unordered reduced tree, l >= n < 2l holds. To the best of our knowledge this is the first of such a compact representation for unordered reduced trees. From the theoretical point of view, the length of the representation gives us an upper bound of the number of unordered reduced trees with l leaves. Precisely, the number of unordered reduced trees with l leaves is at most 2(2l-2) for l >= 1. Moreover, the encoding and decoding can be done in linear time. Therefore, from the practical point of view, our representation is also useful to store a lot of unordered reduced trees efficiently. We also apply the scheme for computing a compact representation to cographs and series-parallel graphs. We show that each of cographs with n vertices has a compact representation in 2n - 1 bits, and the number of cographs with n vertices is at most 2(2n-1). The resulting number is close to the number of cographs with n vertices obtained by the enumeration for small n that approximates Cd-n/n(3)/(2), where C = 0.4126 ... and d = 3.5608 ... . series-parallel graphs are well-investigated in the context of the graphs of bounded treewidth. We give a method to represent a series-parallel graph with m edges in [2.5285m - 2] bits. Hence the number of series-parallel graphs with m edges is at most 2([2.5285m-2]). As far as the authors know, this is the first non-trivial r

关键词： Cograph compact representation counting encoding/decoding scheme series-parallel graph unordered reduce tree

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with precedence constraints and position-dependent processing times

引用

APPLIED MATHEMATICAL MODELLING 2013年第3期37卷 649-658页

作者： Wang, Ji-Bo Wang, Jian-Jun Shenyang Aerosp Univ Sch Sci Shenyang 110136 Peoples R China Dalian Univ Technol Fac Management & Econ Dalian 116024 Peoples R China

In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Scheduling Single-machine Position-dependent processing times parallel chains series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：