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

On r-acyclic edge colorings of planar graphs

DISCRETE APPLIED MATHEMATICS 2012年第13-14期160卷 2048-2053页

作者： Zhang, Xin Wang, Guanghui Yu, Yong Li, Jinbo Liu, Guizhen Shandong Univ Sch Math Jinan 250100 Peoples R China Xidian Univ Dept Math Xian 710071 Peoples R China China Univ Min & Technol Coll Sci Xuzhou 221116 Peoples R China

A proper edge coloring of G is r-acyclic if every cycle C contained in G is colored with at least min{vertical bar C vertical bar, r} colors. The r-acyclic chromatic index of a graph, denoted by a(r)'(G), is the minimum number of colors required to produce an r-acyclic edge coloring. In this paper, we study 4-acyclic edge colorings by proving that a(4)' (G) <= 37 Delta(G) for every planar graph, a(4)' (G) <= max{2 Delta(G), 3 Delta(G) - 4} for every series-parallel graph and a(4)' (G) <= 2 Delta(G) for every outerplanar graph. In addition, we prove that every planar graph with maximum degree at least r and girth at least 5r + 1 has a(r)'(G) = Delta(G) for every r >= 4. (C) 2012 Elsevier B.V. All rights reserved.

关键词： r-acyclic edge coloring Planar graph series-parallel graph Outerplanar graph

来源：评论

学校读者我要写书评

暂无评论

Vertex and tree arboricities of graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2004年第3期8卷 295-306页

作者： Chang, GJ Chen, CY Chen, YP Natl Taiwan Univ Dept Math Taipei 106 Taiwan Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

This paper studies the following variations of arboricity of graphs. The vertex ( respectively, tree) arboricity of a graph G is the minimum number va( G) ( respectively, ta( G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest ( respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.

关键词： arboricity acyclic tree block-cactus graph series-parallel graph cograph girth planar graph hamiltonian cycle

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Free De Morgan Bisemigroups and Bisemilattices

引用

代数集刊（英文版） 2003年第1期10卷 23-32页

作者： Z.(E)sik Department of Computer Science University of Szeged Hungary

We give a geometric representation of free De Morgan bisemigroups,free commutative De Morgan bisemigroups, and free De Morgan bisemilattices by using labeled graphs.

关键词： bisemigroup bisemilattice free algebra De Morgan's laws cograph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Network Characterizations for Excluding Braess's Paradox

引用

THEORY OF COMPUTING SYSTEMS 2016年第4期59卷 747-780页

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

Braess's paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve the 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 strengthen Milchtaich's series-parallel characterization (Milchtaich, Games Econom. Behav. 57(2), 321-346 (2006)) for the single-commodity undirected case.

关键词： Nonatomic selfish routing Braess's paradox Single-commodity network Multcommodity network series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Partitioning graphs of supply and demand

引用

DISCRETE APPLIED MATHEMATICS 2009年第12期157卷 2620-2633页

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

Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G does not have such a partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees - that is, graphs with bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Demand graph partition problem series-parallel graph Supply Partial k-tree

来源：评论

学校读者我要写书评

暂无评论

Minimumcolor-degreeperfectb-matchings

引用

NETWORKS 2021年第4期77卷 477-494页

作者： Anapolska, Mariia Buesing, Christina Comis, Martin Krabs, Tabea Rhein Westfal TH Aachen Lehrstuhl Math 2 Pontdriesch 10-12 D-52062 Aachen Germany

The minimum color-degree perfectb-matching problem (Col-BM) is a new extension of the perfectb-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfectb-matching that are incident to the same node. We show that Col-BM isNP-hard on bipartite graphs by a reduction from (3,B2)-Sat, and conclude that there exists no(2 - epsilon)-approximation algorithm unlessP=NP. However, we identify a class of two-colored complete bipartite graphs on which we can solve Col-BM in polynomial time. Furthermore, we use dynamic programming to devise polynomial-time algorithms solving Col-BM with a fixed number of colors on series-parallel graphs and simple graphs with bounded treewidth.

关键词： bounded treewidth complexity dynamic programming edge-colored graph b-matching series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

OPTIMUM COMMUNICATION SPANNING-TREES IN series-parallel NETWORKS

引用

SIAM JOURNAL ON COMPUTING 1985年第4期14卷 915-925页

作者： ELMALLAH, ES COLBOURN, CJ UNIV WATERLOO DEPT COMP SCIWATERLOO N2L 3G1ONTARIOCANADA

The optimum communication spanning tree problem is to locate a spanning tree which minimizes the sum of the lengths of the shortest routes between all pairs of vertices in a graph, weighted by traffic requirements. Although NP-complete in general, this problem has an efficient solution for series-parallel graphs when all requirements are equal. This problem was introduced by Hu, who gave an efficient solution for the restricted case when the network is complete and the distances are equal.

关键词： spanning tree network design series-parallel graph 2-tree

来源：评论

学校读者我要写书评

暂无评论

Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2005年第4-5期16卷 407-421页

作者： Dubois, D Fargier, H Fortin, J Univ Toulouse 3 IRIT F-31062 Toulouse France

In project management, three quantities are often used by project managers: the earliest starting date, the latest starting date and the float of tasks. These quantities are computed by the Program Evaluation and Review Techniques/Critical Path Method (PERT/CPM) algorithm. When task durations are ill known, as is often the case at the beginning of a project, they can be modeled by means of intervals, representing the possible values of these task durations. With such a representation, the earliest starting dates, the latest starting dates and the floats are also intervals. The purpose of this paper is to give efficient algorithms for their computation. After recalling the classical PERT/CPM problem, we present several properties of the concerned quantities in the interval-valued case, showing that the standard criticality analysis collapses. We propose an efficient algorithm based on path enumeration to compute optimal intervals for latest starting times and floats in the general case, and a simpler polynomial algorithm in the case of series-parallel activity networks.

关键词： PERT CPM earliest starting date latest starting date float series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

The line index and minimum cut of weighted graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第3期109卷 672-685页

作者： Xu, SJ Rutgers State Univ RUTCOR New Brunswick NJ 08903 USA

In this paper we discuss the line index and the minimum capacity, sum of the weights in a minimum cut, of weighted graphs, relationships between the line index and the minimum capacity, between the two kinds of minimum capacities, and between graphs with only negative weights and graphs with both positive weights and negative weights. We provide linear algorithms for both the line index and the minimum capacity of series-parallel graphs. We discuss simplifications in computing the line index and the minimum capacity of weighted graphs. We show that the generalization of algorithm of Orlova and Dorfman, and Hadlock to mixed graphs is just one step. We also discuss the k-approximation of the minimum capacity. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： weighted graph minimum cut balanced graph line index planar graph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：