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

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

来源：评论

学校读者我要写书评

暂无评论

The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times

引用

IIE TRANSACTIONS 2007年第5期39卷 539-557页

作者： Shabtay, Dvir Kaspi, Moshe Steiner, George Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel McMaster Univ Michael G DeGroote Sch Business Management Sci & Informat Syst Area Hamilton ON L8S 4M4 Canada

We extend the classical no-wait two-machine flow shop scheduling problem to the case where job-processing times are controllable through the allocation of a common, limited and nonrenewable resource. Our objective is to simultaneously determine the sequence of the jobs and the resource allocation for each job on both machines in order to minimize the makespan. By using the equivalent load method to obtain the optimal resource allocation on a series-parallel graph, we reduce the problem to a sequencing one and show that it is equivalent to a new special case of the Traveling Salesman Problem (TSP). We prove that although the reduced problem forms a subclass of the TSP on permuted Monge matrices, it is still strongly NP-hard. We provide an approximation result and present three special cases which are polynomially solvable. We have also tested two different subtour-patching heuristics in large-scale computational experiments on randomly generated instances of the problem. Both heuristics produced close-to-optimal solutions in most cases.

关键词： flow shop scheduling no-wait convex resource consumption function series-parallel graph TSP on k-root cost matrices

来源：评论

学校读者我要写书评

暂无评论

Maximum series-parallel Subgraph

引用

ALGORITHMICA 2012年第1-2期63卷 137-157页

作者： Calinescu, Gruia Fernandes, Cristina G. Kaul, Hemanshu Zelikovsky, Alexander IIT Dept Comp Sci Chicago IL 60616 USA Univ Sao Paulo Dept Comp Sci BR-05508090 Sao Paulo Brazil IIT Dept Appl Math Chicago IL 60616 USA Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

关键词： series-parallel graph Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On cyclically orientable graphs

引用

DISCRETE MATHEMATICS 2008年第1期308卷 129-135页

作者： Gurvich, Vladimir Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

graph G is called cyclically orientable (CO) if it admits an orientation in which every simple chordless cycle is cyclically oriented. This family of graphs was introduced by Barot et al. [Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (3) 73 (2006) 545-564]. The authors obtained several nice characterizations of CO-graphs, being motivated primarily by their applications in cluster algebras. Here we obtain several new characterizations that provide algorithms for recognizing CO-graphs and obtaining their cyclic orientations in linear time. We show that the edge maximal CO-graphs are 2-trees;that is, G = (V, E) is a 2-tree if and only if G is CO and G' = (V, E') is not CO whenever E is a proper subset of E'. (c) 2007 Elsevier B.V. All rights reserved.

关键词： cluster algebra graph chromatic number planar graph series-parallel graph cycle chord chordless cycle orientation cyclic orientation 2-tree

来源：评论

学校读者我要写书评

暂无评论

A Brooks-type bound for squares of K₄-minor-free graphs

引用

DISCRETE MATHEMATICS 2009年第23-24期309卷 6572-6584页

作者： Kostochka, Alexandr V. Ozkahya, Lale Woodall, Douglas R. Univ Nottingham Sch Math Sci Nottingham NG7 2RD England Sobolev Inst Math Novosibirsk Russia Univ Illinois Dept Math Urbana IL 61801 USA

Refining a bound by Lih, Wang and Zhu, we prove that if the square G(2) of a K-4-minor-free graph G with maximum degree Delta >= 6 does not contain a complete subgraph on [3/2 Delta] + 1 vertices, then G(2) is [3/2... 详细信息

关键词： Chromatic number Vertex coloring Brooks-type bound Square of a graph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

SIMPLE ENUMERATION OF MINIMAL CUTSETS SEPARATING 2 VERTICES IN A CLASS OF UNDIRECTED PLANAR graphS

引用

IEEE TRANSACTIONS ON RELIABILITY 1992年第1期41卷 63-71页

作者： SUNG, CS YOO, BK Korea Advanced Institute of Science and Technology Seoul South Korea

This paper deals with the problem of enumerating all the s-t minimal cutsets separating two vertices s and t specified in a class of undirected planar graphs, called D-S (delta-star) reducible graphs. The problem is handled by a new enumeration approach based on graph reductions that preserve minimal cutsets such that a graph with complex structure is transformed into a single edge connecting s and t by recursive applications of the mixture of series, parallel, and delta-to-star reductions. Some classes of undirected planar graphs, such as series-parallel and wheel graphs, are identified to be D-S reducible. The approach is provided with a polynomial-time (measured in total number of vertices) enumeration algorithm which is illustrated with a numerical example. The efficiency is shown through some computational experience.

关键词： MINIMAL CUTSET DELTA-TO-STAR REDUCTION series-parallel graph ALGORITHM

来源：评论

学校读者我要写书评

暂无评论

Polynomial algorithms for some scheduling problems with one nonrenewable resource

引用

RAIRO-OPERATIONS RESEARCH 2021年第6期55卷 3493-3511页

作者： Sahli, Abderrahim Carlier, Jacques Moukrim, Aziz Univ Gustave Eiffel COSYS GRETTIA CNRS ESIEE Paris F-77454 Marne La Vallee France Univ Technol Compiegne Sorbonne Univ CNRS Lab Heudiasyc UMR 7253 CS 60 319 F-60203 Compiegne France

This paper deals with the Extended Resource Constrained Project Scheduling Problem (ERCPSP) which is defined by events, nonrenewable resources and precedence constraints between pairs of events. The availability of a resource is depleted and replenished at the occurrence times of a set of events. The decision problem of ERCPSP consists of determining whether an instance has a feasible schedule or not. When there is only one nonrenewable resource, this problem is equivalent to find a feasible schedule that minimizes the number of resource units initially required. It generalizes the maximum cumulative cost problem and the two-machine maximum completion time flow-shop problem. In this paper, we consider this problem with some specific precedence constraints: parallel chains, series-parallel and interval order precedence constraints. For the first two cases, polynomial algorithms based on a linear decomposition of chains are proposed. For the third case, a polynomial algorithm is introduced to solve it. The priority between events is defined using the properties of interval orders.

关键词： Scheduling problems nonrenewable resource decomposition method series-parallel graph interval order graph

来源：评论

学校读者我要写书评

暂无评论

Minimum Spanning Tree Problem with Label Selection

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2011年第2期E94D卷 233-239页

作者： Fujiyoshi, Akio Suzuki, Masakazu Ibaraki Univ Dept Comp & Informat Sci Hitachi Ibaraki 3168511 Japan Kyushu Univ Grad Sch Math Fukuoka 8190395 Japan

In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.

关键词： minimum spanning tree problem NP-hardness series-parallel graph mathematical OCR

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

STRICTLY OPTIMAL SCHEDULES FOR THE CUMULATIVE COST-OPTIMAL SCHEDULING PROBLEM

引用

COMPUTING 1980年第1期24卷 61-86页

作者： ABDELWAHAB, HM KAMEDA, T UNIV WATERLOO DEPT ELECT ENGNWATERLOO N2L 3G1ONTARIOCANADA

Given a set ofn events (or jobs) which are constrained by a precedence relation, we want to order them into a totally ordered sequence (i. e., one machine schedule). Each event has an integer cost (which may be negative) associated with it, and our objective is to minimize the maximum cumulative cost within a schedule, i. e., to obtain a cumulative cost-optimal schedule. We introduce the concept of “strict optimality” and investigate properties of strictly optimal schedules. The usefulness of these schedules is demonstrated in the special case where the precedence relation is “series-parallel”. For this case we describe an algorithm which finds a cumulative cost-optimal schedule inO (n logn) time.

关键词： algorithm complexity job precedence Schedule scheduling sequencing series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：