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

When Can Graph Hyperbolicity be Computed in Linear time?

algorithmICA 2019年第5期81卷 2016-2045页

作者： Fluschnik, Till Komusiewicz, Christian Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Talmon, Nimrod TU Berlin Fak 4 Algorithm & Computat Complex Berlin Germany Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Durham Dept Comp Sci Durham England Ben Gurion Univ Negev Beer Sheva Israel

Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms used in practice for computing the hyperbolicity number of an n-vertex graph have running time O(n(4)). Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2(O(k)) + O(n + m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential time Hypothesis (SETH) fails, there is no 2(o(k)) . n(2-epsilon)-time algorithm for every epsilon > 0.

关键词： Parameterized complexity polynomial-time algorithm FPT in P Strong Exponential time Hypothesis Vertex cover number Cographs

来源：评论

学校读者我要写书评

暂无评论

Linear Arboricity of Outer-1-Planar Graphs

引用

Journal of the Operations Research Society of China 2021年第1期9卷 181-193页

作者： Xin Zhang Bi Li School of Mathematics and Statistics Xidian UniversityXi’an 710071China

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most *** et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=*** is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.

关键词： Outer-1-planar graph Crossing Linear arboricity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON SINGLE-PROCESSOR SCHEDULING WITH time-DEPENDENT EXECUTION timeS

引用

OPERATIONS RESEARCH LETTERS 1995年第3期17卷 127-129页

作者： CHEN, ZL Department of Civil Engineering and Operations Research Princeton University Princeton NJ 08544 USA

We consider a single-processor scheduling model where the execution time of a task is a decreasing linear function of its starting time. The complexity of the problem of minimizing the number of late tasks remains unknown for a set of tasks with identical due dates. We present an O(n(2))-time dynamic programming algorithm for solving this problem.

关键词： SCHEDULING SINGLE-PROCESSOR DYNAMIC PROGRAMMING polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Single machine batch scheduling with non-increasing time slot costs

引用

OPTIMIZATION LETTERS 2022年第6期16卷 1817-1833页

作者： Ren, Junfeng Northeastern Univ Minist Educ Key Lab Data Analyt & Optimizat Smart Ind Shenyang 110819 Peoples R China Henan Polytech Univ Sch Math & Informat Sci Jiaozuo 454000 Henan Peoples R China

This work studies batch scheduling problems in which non-increasing time slot costs are taken into consideration on a single machine. In these problems, each batch occupies some time slots, and the cost yielded by batch setup and job processing in a batch is dependent on the time slots. The objective is to minimize the sum of the total time slot cost and one of the traditional performance measures, including the total flow time, maximum lateness/tardiness, and weighted number of tardy jobs. For these objectives, it is necessary to determine not only the optimal job sequence and batch partition but also the optimal time slot allocation for the batches. For each problem, we find the structured properties of the optimal schedule and then propose an algorithm based on dynamic programming. All the presented algorithms are of polynomial time if the input size of the time slot costs is O(K).

关键词： polynomial-time algorithm time slot cost Batch Scheduling

来源：评论

学校读者我要写书评

暂无评论

Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 250卷 130-144页

作者： Brandstaedt, Andreas Giakoumakis, Vassilis Milanic, Martin Univ Rostock Inst Informat D-18051 Rostock Germany Univ Picardie Jules Verne MIS Amiens France Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for claw-free graphs, for 2P(3)-free chordal graphs (and thus, for P-7-free graphs), and for bipartite graphs. For the complexity of ED and its weighted version WED, a dichotomy for H-free graphs was reached: A graph H is called a linear forest if H is acyclic and claw-free, that is, if all its components are paths. Thus, the ED problem remains NP-complete for H-free graphs whenever H is not a linear forest. For every linear forest H, WED is either solvable in polynomial time or NP-complete for H-free graphs;the final result showed that WED is solvable in polynomial time for P-6-free graphs. For (H-1 , H-2)-free graphs, however, we are still far away from a dichotomy result. The main topics of this paper are: (1) to improve the time bounds and simplify the proofs (based on modular decomposition) for polynomial time cases of WED for some H-free graph classes;(2) to investigate the complexity of WED for some cases of (H-1 , H-2)-free graphs such that WED is NP-complete for Hi-free graphs for at least one of i e (1, 2}. Since it is well known that WED is solvable in polynomial time for graph classes of bounded clique width, we consider only classes of (H-1, H-2)-free graphs with unbounded clique-width. (C) 2018 Published by Elsevier B.V.

关键词： Weighted efficient domination Modular decomposition H-free graphs Linear forest (H-1 , H-2)-free graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Counting the different efficient paths for transportation networks and its applications

引用

JOURNAL OF ADVANCED TRANSPORTATION 2005年第2期39卷 193-220页

作者： Meng, Q Lee, DH Cheu, RL Natl Univ Singapore Dept Civil Engn Singapore 117548 Singapore

This paper deals with an interesting problem about how to efficiently compute the number of different efficient paths between an origin-destination pair for a transportation network because these efficient paths are the possible paths used by drivers to some extent. Based on a novel triangle operation derived, it first presents a polynomial-time combinatorial algorithm that can obtain the number of different simple paths between any two nodes for an acyclic network as well as the total travel cost of these paths. This paper proceeds to develop a combinatorial algorithm with polynomial-time complexity for both counting the different efficient paths between an origin-destination pair and calculating the total travel cost of these paths. As for applications, this paper shows that the preceding two algorithms can yield the lower and upper bounds for the number of different simple paths between an origin-destination pair, while it has already be recognized that a polynomial-time algorithm getting such a number does not exist for a general network. Furthermore, the latter algorithm can be applied for developing a heuristic method for the traffic counting location problem arising from the origin-destination matrix estimation problems.

关键词： counting the simple path polynomial-time algorithm #P-complete problem the efficient path traffic counting location problem

来源：评论

学校读者我要写书评

暂无评论

Recognition of tractable satisfiability problems through balanced polynomial representations

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期99卷 229-244页

作者： Warners, JP van Maaren, H Delft Univ Technol Fac Informat Technol & Syst Dept Tech Math & Informat NL-2600 GA Delft Netherlands CWI SEN2 NL-1090 GB Amsterdam Netherlands

We consider a specific class of satisfiability (SAT) problems, the conjunctions of (nested) equivalencies (CoE). It is well known that CNF (conjunctive normal form) translations of CoE formulas are hard for branching and resolution algorithms. Tseitin proved that regular resolution requires a running time exponential in the size of the input. We review a polynomial time algorithm for solving CoE formulas, and address the problem of recognizing a CoE formula by its CNF representation. Making use of elliptic approximations of 3SAT problems, the so-called doubly balanced 3SAT formulas can be seen to be equivalent to CoE formulas. Subsequently, the notion of doubly balancedness is generalized by using polynomial representations of satisfiability problems, to obtain a general characterization of CoE formulas. We briefly address the problem of finding CoE subformulas, and finally the application of the developed theory to several DIMACS benchmarks is discussed. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： satisfiability conjunctive normal form polynomial functions polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第2期11卷 15-24页

作者： Bacso, Gabor Tuza, Zsolt Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary Univ Pannonia Dept Comp Sci H-8200 Veszprem Hungary

A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size left perpendicular19n/30 + 2/15right perpendicular. This bound is tight, since 19n/30 - 1/15 is a lower bound for infinitely many values of n. We also prove that the vertex set of any connected claw-free graph of maximum degree at most four, other than an odd cycle longer than three, can be partitioned into two clique-transversal sets. The proofs of both results yield polynomial-time algorithms that find corresponding solutions.

关键词： clique-transversal set weak coloring clique coloring cubic graph claw-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

List homomorphisms of graphs with bounded degrees

引用

DISCRETE MATHEMATICS 2007年第3-5期307卷 386-392页

作者： Feder, Tomas Hell, Pavol Huang, Jing Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

In a series of papers, we have classified the complexity of list homomorphism problems. Here, we investigate the effect of restricting the degrees of the input graphs. It turns out that the complexity does not change (except when the degree bound is two). We obtain similar results on restricting the size of the lists. We contrast these results with facts about variants of the list homomorphism problem, where restricting the degrees can have an important effect on the complexity. (c) 2006 Elsevier B.V. All rights reserved.

关键词： homomorphism list homomorphism bi-arc graph edge-asteroid bounded degree H-colouring problem extension problem polynomial-time algorithm NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

The unbounded parallel-batch scheduling with rejection

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2012年第3期63卷 293-298页

作者： Zhang, L. Q. Lu, L. F. Ng, C. T. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Zhengzhou Henan Peoples R China

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs;(2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs;(3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs;(4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them. Journal of the Operational Research Society (2012) 63, 293-298. doi:10.1057/jors.2011.31 Published online 4 May 2011

关键词： parallel-batch scheduling rejection penalty polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：