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

On the Polarity and Monopolarity of Graphs

JOURNAL OF GRAPH THEORY 2014年第2期76卷 138-148页

作者： Churchley, Ross Huang, Jing Univ Victoria Dept Math & Stat Victoria BC V8W 2Y2 Canada

Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions;graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle-free graphs and claw-free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP-complete for triangle-free graphs. We also show that for claw-free graphs the former is NP-complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP-completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw-free graphs uses a subroutine similar to the well-known breadth-first search algorithm and is based on a new structural characterization of monopolar claw-free graphs, a generalization of one for monopolar line graphs obtained earlier.

关键词： NP-completeness characterization polynomial time algorithm claw-free graph monopolar graph triangle-free graph Polar graph

来源：评论

学校读者我要写书评

暂无评论

How many disjoint 2-edge paths must a cubic graph have?

引用

JOURNAL OF GRAPH THEORY 2004年第1期45卷 57-79页

作者： Kelmans, A Mubayi, D Rutgers State Univ New Brunswick NJ 08903 USA Univ Puerto Rico San Juan PR 00936 USA Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA

In this paper we show that every simple cubic graph on n vertices has a set of at least [n/4] disjoint 2-edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set i... 详细信息

关键词： packing 2-edge path cubic graph polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Arc-Disjoint In- and Out-Branchings With the Same Root in Locally Semicomplete Digraphs

引用

JOURNAL OF GRAPH THEORY 2014年第4期77卷 278-298页

作者： Bang-Jensen, Jorgen Huang, Jing Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Victoria Dept Math & Stat Victoria BC Canada

Deciding whether a digraph contains a pair of arc-disjoint in-and out-branchings rooted at a specified vertex is a well-known NP-complete problem (as proved by Thomassen, see [2]). This problem has been shown to be polynomial time solvable for semicomplete digraphs [2] and for quasi-transitive digraphs [6]. In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc-disjoint in-and out-branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from [2] for semicomplete digraphs and solves an open problem from [4]. (C) 2014 Wiley Periodicals, Inc.

关键词： Locally semicomplete digraph structure of locally semicomplete digraphs arc-disjoint in- and out-branchings arc-contraction polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Partial inverse maximum spanning tree in which weight can only be decreased under l_p-norm

引用

JOURNAL OF GLOBAL OPTIMIZATION 2018年第3期70卷 677-685页

作者： Li, Xianyue Zhang, Zhao Du, Ding-Zhu Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.

关键词： Partial inverse problem Spanning tree polynomial time algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

time-optimal interpolation for five-axis CNC machining along parametric tool path based on linear programming

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2013年第5-8期69卷 1373-1388页

作者： Fan, Wei Gao, Xiao-Shan Lee, Chen-Han Zhang, Ke Zhang, Qiang Chinese Acad Sci AMSS Inst Syst Sci KLMM Beijing 100190 Peoples R China Huazhong Univ Sci & Technol Sch Mech Sci & Engn Wuhan 430074 Peoples R China China Univ Petr Qingdao 266555 Peoples R China

In this paper, the time-optimal velocity planning problem for five-axis computer numerical control machining along a given parametric tool path under chord error, acceleration, and jerk constraints is studied. The velocity planning problem under confined chord error, feedrate, and acceleration is reduced to an equivalent linear programming problem by discretizing the tool path and other quantities. As a consequence, a polynomial time algorithm with computational complexity O(N (3.5)) is given to find the optimal solution, where N is the number of discretized segments of the tool path. The velocity planning problem under confined chord error, feedrate, acceleration, and jerk is reduced to a linear programming program by using a linear function to approximate the nonlinear jerk constraint. As a consequence, a polynomial time algorithm is given to find the approximate time-optimal solution. Simulation results are used to show the efficiency and effectiveness of the algorithms.

关键词： time-optimal interpolation Velocity planning Parametric tool path Jerk constraint Linear programming algorithm polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第2期289卷 495-507页

作者： Gharehgozli, Amir Xu, Chao Zhang, Wenda Calif State Univ Northridge David Nazarian Coll Business & Econ Northridge CA 91330 USA Univ Illinois Dept Comp Sci Urbana IL 61820 USA Voleon Grp Berkeley CA 94704 USA Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61820 USA

We describe an algorithm for the high multiplicity asymmetric traveling salesman problem with feedback vertex set of size k (HMATSP-kFVS) where each vertex can be visited a certain number of times and each cycle in a solution contains at least one vertex from the feedback vertex set. We show how it can be used to improve algorithms in automated storage and retrieval systems. An automated storage and retrieval system includes storage blocks and storage and retrieval machines that either move to retrieve unit loads from their current locations in the system to a depot or take unit loads from a depot and store them to specific locations in the system. Given n storage and retrieval requests in a system with k depots and one storage and retrieval machine, we show that our algorithm for HMATSP-kFVS can solve the problem of minimizing total traveling time of the storage and retrieval machine in O(n(k) + n(3)) time when all depots are specialized (each depot fulfills one type of requests) and in O(n(2k) + n(3)) time when depots are regular (each depot fulfills both types of requests). The best previous algorithm only solves the special case of the problem with 2 regular depots in O(n(6)) time. The applicability of our algorithm for several generalizations and special cases of the problem is also discussed. Furthermore, to evaluate the performance of our solution method, we perform extensive numerical experiments. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Logistics OR in maritime industry and warehousing Storage/retrieval system storage High multiplicity ATSP storage polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第2期48卷 15-15页

作者： Fujie, Tetsuya Higashikawa, Yuya Katoh, Naoki Teruyama, Junichi Tokuni, Yuki Univ Hyogo Kobe Japan

This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an O(n42 alpha(n)alpha(n)2logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4 2<^>{\alpha (n)} \alpha (n)<^>2 \log n)$$\end{document} time algorithm, where n is the number of vertices in the network and alpha()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot )$$\end{document} is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to O(n32 alpha(n)alpha(n)logn)\documentclass[12pt]{min

关键词： Minimax regret Facility location problem polynomial time algorithm Path network Dynamic flow

来源：评论

学校读者我要写书评

暂无评论

Well-solvable special cases of the traveling salesman problem: A survey

引用

SIAM REVIEW 1998年第3期40卷 496-546页

作者： Burkard, RE Deineko, VG Van Dal, R Van der Veen, JAA Woeginger, GJ Graz Tech Univ Inst Math A-8010 Graz Austria Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England Chalmers Tekn Hogskola Inst Datavetenskap S-41296 Gothenburg Sweden Nijenrode Univ Netherlands Sch Business NL-3621 BG Breukelen Netherlands

The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].

关键词： traveling salesman problem combinatorial optimization polynomial time algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

Computing Cartan subalgebras of Lie algebras

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1996年第5期7卷 339-349页

作者： DeGraaf, W Ivanyos, G Ronyai, L EINDHOVEN UNIV TECHNOL DEPT MATH & COMP SCINL-5600 MB EINDHOVENNETHERLANDS HUNGARIAN ACAD SCI INST COMP & AUTOMATH-1111 BUDAPESTHUNGARY

We consider the algorithmic problem of computing Cartan subalgebras in Lie algebras over finite fields and algebraic number fields. We present a deterministic polynomial time algorithm for the case when the ground field k is sufficiently large. Our method is based on a solution of a linear algebra problem: the task of finding a locally regular element in a subspace of linear transformations. Also, we give a polynomial time algorithm for restricted Lie algebras over arbitrary finite fields. Both methods require an auxiliary procedure for finding non-nilpotent elements in subalgebras. This problem is also treated. Computational experiences are discussed at the end of the paper.

关键词： Lie algebra Cartan subalgebra symbolic computation polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on scheduling multiprocessor tasks with precedence constraints on parallel processors

引用

INFORMATION PROCESSING LETTERS 1997年第3期63卷 119-122页

作者： Amoura, AK LRI Bât. 490 Université Paris Sud 91405 Orsay Cedex France

The scheduling multiprocessor task system model with precedence constraints on parallel processors is extended. The objective of the problem is the minimization of the makespan. Some polynomically solvable classes of ... 详细信息

关键词： parallel processing scheduling precedence constraints computational complexity polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：