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

On lengths of edge-labeled graph expressions

DISCRETE APPLIED MATHEMATICS 2022年 319卷 583-594页

作者： Korenblit, Mark Levit, Vadim E. Holon Inst Technol Dept Comp Sci Holon Israel Ariel Univ Dept Math Ariel Israel

This paper investigates relationship between algebraic expressions and graphs. Our intent is to simplify graph expressions and eventually find their shortest representations. We prove the monotonicity results allowing to assert that the length of a shortest expression of any subgraph of a given graph is not greater than the length of a shortest expression of the graph. We describe the decomposition method for generating expressions of complete st-dags (two-terminal directed acyclic graphs) and estimate the ( ) corresponding expression complexities. Using these findings, we present an 2(O(log2 n)) upper bound for the length of a shortest expression for every n-vertex st-dag. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Two-terminal directed acyclic graph series-parallel graph Edge-labeled graph Algebraic expression Complexity Decomposition

来源：评论

学校读者我要写书评

暂无评论

Algorithms for core stability, core largeness, exactness, and extendability of flow games

引用

中国高等学校学术文摘·数学 2010年第1期5卷 47-63页

作者： Qizhi FANG Rudolf FLEISCHER Jian LI Xiaoxun SUN Department of Mathematics Ocean University of China Qingdao 266100 China Department of-Computer Science and Engineering Fudan University Shanghai 200433 China Department of Computer Science University of Maryland College Park MD 20742 USA Department of Mathematics and Computing University of Southern Queensland Toowoomba QLD 4350 Australia

We study core stability and some related properties of flow games defined on simple networks (all edge capacities are equal) from an algorithmic point of view. We first present a sufficient and necessary condition that can be tested efficiently for a simple flow game to have a stable core. We also prove the equivalence of the properties of core largeness, extendability, and exactness of simple flow games and provide an equivalent graph theoretic characterization which allows us to decide these properties in polynomial time. Keywords Flow network - series-parallel graph - imputation - cooperative game MSC 91A12 - 91A46 - 05C57

关键词： Flow network series-parallel graph imputation cooperative game

来源：评论

学校读者我要写书评

暂无评论

The Minimum Tollbooth Problem in Atomic Network Congestion Games with Unsplittable Flows

引用

THEORY OF COMPUTING SYSTEMS 2021年第7期65卷 1094-1109页

作者： Nickerl, Julian Ulm Univ Ulm Germany

This work analyzes the minimum tollbooth problem in atomic network congestion games with unsplittable flows. The goal is to place tolls on edges, such that there exists a pure Nash equilibrium in the tolled game that is a social optimum in the untolled one. Additionally, we require the number of tolled edges to be the minimum. This problem has been extensively studied in non-atomic games, however, to the best of our knowledge, it has not been considered for atomic games before. By a reduction from the weighted CNF SAT problem, we show both the NP-hardness of the problem and the W[2]-hardness when parameterizing the problem with the number of tolled edges. On the positive side, we present a polynomial time algorithm for networks on series-parallel graphs that turns any given state of the untolled game into a pure Nash equilibrium of the tolled game with the minimum number of tolled edges.

关键词： Atomic network congestion games Minimum tollbooth problem series-parallel graph Social optimum Unsplittable flow Weighted CNF SAT

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with precedence constraints and decreasing start-time dependent processing times

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2010年第1-4期46卷 291-299页

作者： Gao, Wen-Jun Huang, Xue Wang, Ji-Bo Shenyang Inst Aeronaut Engn Operat Res & Cybernet Inst Sch Sci Shenyang 110136 Peoples R China

In this paper we consider single-machine scheduling problems with decreasing start-time-dependent processing times, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraint, respectively. It is shown that, for the problems of minimization of the total weighted completion time, polynomial algorithms exist.

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

来源：评论

学校读者我要写书评

暂无评论

A method of finding legal sequence number for a class of extended series-parallel digraphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1997年第4期E80A卷 635-642页

作者： Ge, QW Yoshioka, N Faculty of Education Yamaguchi University Yamaguchi-shi 753 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 finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

关键词： topological sorting legal sequence legal sequence number digraph st-DAG series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

On survivable network polyhedra

引用

DISCRETE MATHEMATICS 2005年第2-3期290卷 183-210页

作者： Kerivin, H Mahjoub, AR Univ Clermont Ferrand CNRS UMR 6158 Lab LIMOS F-63177 Aubiere France Univ Minnesota Inst Math & Applicat Minneapolis MN 55455 USA

Given an undirected network G = (V, E), a vector of nonnegative integers r = (r(nu) : nu is an element of V) associated with the nodes of G and weights on the edges of G, the survivable network design problem is to determine a mininium-weight subnetwork of G such that between every two nodes u, v of V, there are at least min {r (u), r(nu)} edge-disjoint paths. In this paper we study the polytope associated with the solutions to that problem. We show that when the underlying network is series-parallel and r(nu) is even for all nu is an element of V, the polytope is completely described by the trivial constraints and the so-called cut constraints. As a consequence, we obtain a polynomial time algorithm for the survivable network design problem in that class of networks. This generalizes and unifies known results in the literature. We also obtain a linear description of the polyhedron associated with the problem in the same class of networks when the use of more than one copy of an edge is allowed. (c) 2004 Elsevier B.V. All rights reserved.

关键词： survivable network polyhedron cut series-parallel graph polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

引用

COMPUTERS & OPERATIONS RESEARCH 2006年第10期33卷 3015-3033页

作者： Kaspi, M Shabtay, D Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used;thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： bicriterion single machine scheduling convex resource allocation time/cost trade-offs series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Distance constrained labelings of K₄-minor free graphs

引用

DISCRETE MATHEMATICS 2009年第18期309卷 5745-5756页

作者： Kral', Daniel Nejedly, Pavel Charles Univ Prague Dept Appl Math Fac Math & Phys CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci Fac Math & Phys CR-11800 Prague Czech Republic

Motivated by previous results on distance constrained labelings and coloring of squares of K-4-minor free graphs, we show that for every p >= q >= 1 there exists Delta(0) such that every K-4-minor free graph G with maximum degree Delta >= Delta(0) has an L(p, q)-labeling of span at most qleft perpendicular3 Delta(G)/2right perpendicular. The obtained bound is the best possible. (C) 2008 Elsevier B.V. All rights reserved.

关键词： K-4-minor free graph series-parallel graph Distance constrained labeling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：