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

MINIMIZING MAXIMUM LATENESS IN A 2-MACHINE OPEN SHOP

MATHEMATICS OF OPERATIONS RESEARCH 1981年第1期6卷 153-158页

作者： LAWLER, EL LENSTRA, JK KAN, AHGR MATH CENTRUM NL-1005 AMSTERDAMNETHERLANDS ERASMUS UNIV ROTTERDAMNETHERLANDS

We consider the problem of scheduling independent jobs in a two-machine open shop so as to minimize the maximum lateness with respect to due dates for the jobs. For the case in which preemption is allowed, a linear-ti... 详细信息

关键词： two-machine open shop due dates maximum lateness preemptive scheduling nonpreemptive scheduling linear-time algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

algorithmic results in secure total dominating sets on graphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 918卷 1-17页

作者： Poureidi, Abolfazl Shahrood Univ Technol Fac Math Sci Shahrood Iran

Given a graph G = (V, E), a (total) dominating set of G is a subset D & SUBE;V such that each vertex in V \ D (respectively, V ) is adjacent to at least one vertex in D. A (total) dominating set D of G is a secure (total) dominating set if for each v & ISIN;V \ D there is a vertex u & ISIN;D adjacent to v such that (D \ {u}) & OR;{v} is also a (total) dominating set of G. The minimum cardinality of a secure (total) dominating set of G is called the secure (total) domination number of G. The secure (total) domination problem is to find a minimum secure (total) dominating set of any graph. In this paper, we study the secure total domination problem. We show that the problem restricted to trees is solvable in linear-time, the decision version of the problem is NP-complete for circle graphs, the complexity of the problem differs from that of the secure domination problem, and the problem is APX-complete for graphs of degree at most 4. Furthermore, we show that the optimization version of the problem on bipartite graphs cannot be approximated in polynomial time within (1 - epsilon)ln | V | for any epsilon > 0, unless NP & SUBE;Dtime(|V |(O (log log |V |))). (c) 2022 Elsevier B.V. All rights reserved.

关键词： Secure total dominating set linear-time algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Optimization of functions with rank-two variation over a box

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2005年第3期161卷 598-617页

作者： Bomze, IM Telekom Austria AG Business & Market Res Operat Res A-1020 Vienna Austria

This paper deals with optimization of functions that depend on (large-scale) data via a linear transformation of rank two. An algorithm is presented which-under mild assumptions-finds the global solution with polynomial-time complexity in the worst case, provided the critical points of the objective can be controlled with the same effort. Moreover, for important subclasses of objectives including the linear-fractional, and the quadratic case, we arrive at a linear-time algorithm. For both cases, small simulation studies are provided to illustrate the average case runtime behaviour. As a possible application, sensitivity of cost assessment in communication networks is addressed where the problems may have tens of thousands of variables. (C) 2003 Elsevier B.V. All rights reserved.

关键词： nonlinear programming large scale optimization linear-time algorithm telecommunication

来源：评论

学校读者我要写书评

暂无评论

Colourful components in k-caterpillars and planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 895卷 137-150页

作者： Chlebikova, Janka Dallard, Clement Univ Portsmouth Sch Comp Portsmouth Hants England Univ Primorska FAMNIT Koper Slovenia

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph G and an integer p, the COLOURFUL COMPONENTS problem asks whether there exist at most p edges whose removal makes G colourful and the COLOURFUL PARTITION problem asks whether there exists a partition of G into at most p colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on k-caterpillars, which are trees with a central path P such that every vertex not in P is within distance k from a vertex in P. We prove that COLOURFUL COMPONENTS and COLOURFUL PARTITION are NP-complete on 4-caterpillars with maximum degree 3, 3-caterpillars with maximum degree 4 and 2caterpillars with maximum degree 5. On the other hand, we show that the problems are linear-time solvable on 1-caterpillars. Hence, our results imply two complexity dichotomies on trees: COLOURFUL COMPONENTS and COLOURFUL PARTITION are linear-time solvable on trees with maximum degree d if d <= 2 (that is, on paths), and NP-complete otherwise;COLOURFUL COMPONENTS and COLOURFUL PARTITION are linear-time solvable on k-caterpillars if k <= 1, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on k-caterpillars, for every non-negative integer k, with respect to the maximum degree. We also show that COLOURFUL COMPONENTS is NP-complete on 5-coloured planar graphs with maximum degree 4 and on 12-coloured planar graphs with maximum degree 3. Our results answer two open questions of Bulteau et al. mentioned in Bulteau et al. (2019) [6]. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Colorful component Trees Planar graphs NP-complete linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Long paths in hypercubes with a quadratic number of faults

引用

INFORMATION SCIENCES 2009年第21期179卷 3763-3771页

作者： Dvorak, Tomas Koubek, Vaclav Charles Univ Prague Fac Math & Phys CR-11800 Prague Czech Republic

A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set off faulty vertices is called long if its length is at least 2(n) - 2f - 2. We present a function phi(n) = Theta(n(2)) such that if f <= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n). Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f <= phi(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length. (c) 2009 Elsevier Inc. All rights reserved.

关键词： Faulty vertex Hypercube linear-time algorithm Long path

来源：评论

学校读者我要写书评

暂无评论

SOME CHAIN VISIBILITY PROBLEMS IN A SIMPLE POLYGON

引用

algorithmICA 1990年第4期5卷 485-507页

作者： LEE, SH CHWA, KY KOREA INST SCI & TECHNOL DEPT COMP SCI SEOUL 130650 SOUTH KOREA

In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.

关键词： Computational geometry linear-time algorithm Simple polygon Visibility

来源：评论

学校读者我要写书评

暂无评论

Fast connected-component labeling

引用

PATTERN RECOGNITION 2009年第9期42卷 1977-1987页

作者： He, Lifeng Chao, Yuyan Suzuki, Kenji Wu, Kesheng Aichi Prefectural Univ Grad Sch Informat Sci & Technol Aichi 4801198 Japan Nagoya Sangyo Univ Grad Sch Environm Management Aichi 4888711 Japan Univ Chicago Div Biol Sci Dept Radiol Chicago IL 60637 USA Univ Calif Berkeley Lawrence Berkeley Lab Berkeley CA 94720 USA ShaanXi Univ Sci & Technol Xian 710021 Shannxi Peoples R China

Labeling of connected components in a binary image is one of the most fundamental operations in pattern recognition: labeling is required whenever a computer needs to recognize objects (connected components) in a binary image. This paper presents a fast two-scan algorithm for labeling of connected components in binary images. We propose an efficient procedure for assigning provisional labels to object pixels and checking label equivalence. Our algorithm is very simple in principle, easy to implement, and suitable for hardware and parallel implementation. We show the correctness of our algorithm, analyze its complexity, and compare it with other labeling algorithms. Experimental results demonstrated that our algorithm is superior to conventional labeling algorithms. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Labeling algorithm Label equivalence Connected component linear-time algorithm Pattern recognition

来源：评论

学校读者我要写书评

暂无评论

A note on the subgraphs of the (2 x ∞)-grid

引用

DISCRETE MATHEMATICS 2010年第3期310卷 531-536页

作者： Diaz, Josep Kaminski, Marcin Thilikos, Dimitrios M. Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat ES-08034 Barcelona Spain Univ Libre Bruxelles Dept Comp Sci Brussels Belgium Univ Athens Dept Math GR-15784 Athens Greece

We give a linear-time algorithm checking whether a graph is a subgraph of the (2 x k)-grid for some value of k. Our algorithm is based on a detailed characterization of the structure of such graphs. (C) 2009 Elsevier ... 详细信息

关键词： Partial grids linear-time algorithm Biconnected components

来源：评论

学校读者我要写书评

暂无评论

The stable roommates problem with ties

引用

JOURNAL OF algorithmS 2002年第1期43卷 85-105页

作者： Irving, RW Manlove, DF Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stability. We present a linear-time algorithm for finding a super-stable matching if one exists, given a stable roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given stable roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2. (C) 2002 Elsevier Science (USA).

关键词： stable matching problem indifference super-stability weak stability linear-time algorithm NP-completeness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Sharp threshold for embedding balanced spanning trees in random geometric graphs

引用

JOURNAL OF GRAPH THEORY 2024年第1期107卷 107-125页

作者： Diaz, Alberto Espuny Lichev, Lyuben Mitsche, Dieter Wesolek, Alexandra Tech Univ Ilmenau Inst Math Ilmenau Germany Univ Jean Monnet Inst Camille Jordan St Etienne France Pont Univ Catolica IMC Santiago Chile Simon Fraser Univ Dept Math Burnaby BC Canada

A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of balanced spanning trees in the random geometric graph G(n,r,d) ${\mathscr{G}}(n,r,d)$. In particular, we find the sharp threshold for balanced binary trees. More generally, we show that all sequences of balanced trees with uniformly bounded degrees and height tending to infinity appear above a sharp threshold, and none of these appears below the same value. Our results hold more generally for geometric graphs satisfying a mild condition on the distribution of their vertex set, and we provide a polynomial time algorithm to find such trees.

关键词： linear-time algorithm random geometric graphs sharp threshold spanning trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：