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

10th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Mondal, Joyashree Vijayakumar, S. Indian Inst Informat Technol Design & Mfg IIITDM Chennai 600127 India

ISBN: (纸本)9783031522123;9783031522130

A graph that is isomorphic to K-1,K- r for some r >= 0 is called a star. For a graph G = (V, E), any subset S of its vertex set V is called a star of G if the subgraph induced by S is a star. A collection C = {V-1, . . . , V-k} of stars in G is called a star cover of G if V-1 boolean OR. . . boolean OR V-k = V. A star cover C of G is called a star partition of G if it is also a partition of V. Given a graph G, the problem STAR COVER asks for a star cover of G of minimum size. Given a graph G, the problem STAR PARTITION asks for a STAR PARTITION of G of minimum size. Both the problems are NP-hard even for bipartite graphs [24]. In this paper, we obtain exact O(n(2)) time algorithms for both STAR COVER and STAR PARTITION on (C-4, P-4)-free graphs and on (2K(2), P-4)-free graphs. We also prove that STAR COVER and STAR PARTITION are polynomially equivalent, up to the optimum value, for butterfly-free graphs and present an O(n(14)) time O(log n)-approximation algorithm for these equivalent problems on butterfly-free graphs. We also obtain O(log n)-approximation algorithms for STAR COVER on hereditary graph classes.

关键词： Star Cover Star Partition Cographs Butterfly-free Graphs polynomial time algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Graph augmentation problems with degree-unchangeable vertices

Graph augmentation problems with degree-unchangeable vertice...

引用

13th Workshop on Circuits and Systems

作者： Mashima, T Watanabe, T Hiroshima City Univ Fac Informat Sci Dept Comp Engn Hiroshima 7313194 Japan Hiroshima Univ Fac Engn Dept Circuits & Syst Higashihiroshima 7398527 Japan

The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G,S,D), is defined as follows: "Given a positive integer k, an undirected graph G = (V: E), a specified set of vertices S subset of or equal to V and a set of degree-changeable vertices D subset of or equal to V, find a smallest set of edges E' such that the vertex-connectivity of S in (V, E boolean OR E') is at least I;and E' subset of or equal to {(u,v) / u,v is an element of D}." The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G, S, D) or 3VCA(G, S, D) can be done in O(/V/ + /E/) or O(/V/(/V/ + /E/)) time, respectively.

关键词： graphs connectivity augmentation vertex-connectivity degree-unchangeable vertices polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

On Star Partition of Split Graphs 10th

On Star Partition of Split Graphs

引用

10th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Divya, D. Vijayakumar, S. Indian Inst Informat Technol Design & Mfg IIITDM Chennai 600127 India

ISBN: (纸本)9783031522123;9783031522130

A graph that is isomorphic to K-1,K- r for some r >= 0 is called a star. A partition {V-1, . . . , V-k} of the vertex set of a graph G into k sets is called a star partition of G of size k if each set in the partition induces a star. The minimum k for which a graph G admits a star partition of size k is called the star partition number of G and is denoted by sp(G). Given a graph G, the problem Min StarPartition asks for a star partition of G of minimum size. Given a graph G and a positive integer k, its decision version Star Partition asks whether sp(G) <= k. Star Partition is NP-complete for many natural graph classes [25]. In particular, it is NP-complete for K-1,K-5-free split graphs. In this paper, we study the star partition problems on split graphs, with a special focus on the degrees of vertices in the independent part. We call a split graph (a) an r-split graph if each vertex in the independent part has degree r and (b) an (r(1), . . . , r(k))-split graph if each vertex in the independent part has degree equal to one of r(1), . . . , r(k). We obtain the following NP-completeness results: (1) Star Partition is NP-complete even for K-1,K-5-free 2-split graphs. (2) Deciding whether sp(G) = inverted right perpendicular omega(G)/2 inverted left perpendicular is NP-complete even for K-1,K-6-free 2-split graph (sp(G) >= inverted right perpendicula omega(G)/2 inverted left perpendicular for any graph G). (3) Star Partition is NP-complete even for (1, r)-split graphs (r >= 2 and is fixed). We obtain the following fixed parameter (in)tractability results (in each case, k stands for the parameter) (1) Given any connected split graph G and an integer k >= 1, deciding whether sp(G) <= k is fixed parameter tractable and has an O((2k)(2k+1) n) time algorithm. (2) Given a graph G and an integer k >= 0, deciding whether sp(G) <= inverted right perpendicular omega(G)/2 inverted left perpendicular + k is para-NP-hard even when restricted to either (a) K-1,K-6-free (0, 2)-split

关键词： Star Partition Split Graphs NP-completeness polynomial time algorithms Fixed Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for ridesharing of personal vehicles 11th

Efficient algorithms for ridesharing of personal vehicles

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Gu, Qian-Ping Liang, Jiajian Leo Zhang, Guochuan Simon Fraser Univ Sch Comp Sci Burnaby BC Canada Zhejiang Univ Coll Comp Sci & Technol Hangzhou Zhejiang Peoples R China

ISBN: (纸本)9783319711492

Given a set of trips in a road network, where each trip has an individual, a vehicle and some requirements, the ridesharing problem is to select a subset of vehicles to deliver the individuals of all trips to their destinations satisfying the requirements. Common requirements of a trip include the source, destination, vehicle capacity, detour distance limit, preferred paths, and time constraints of the trip. Minimizing the total travel distance of the vehicles and minimizing the number of vehicles are major optimization goals. These minimization problems are complex and NA-hard because each trip may have many requirements. We study simplified minimization problems in which each trip's requirements are specified by the source, destination, vehicle capacity, detour distance and preferred path parameters. We show that both minimization problems can be solved in polynomial time if all of the following conditions are satisfied: (1) all trips have the same destination or same source: (2) no detour is allowed and (3) each trip has one unique preferred path. It is known that both minimization problems are NP-hard if any one of the three conditions is not satisfied. Our results and the NP-hard results suggest a boundary between the polynomial time solvable cases and NP-hard cases for the minimization problems. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Ridesharing problem Optimization problems polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Contracting chordal graphs and bipartite graphs to paths and trees

Contracting chordal graphs and bipartite graphs to paths and...

引用

6th Latin American algorithms Graphs and Optimization Symposium (LAGOS11)6th Latin American algorithms Graphs and Optimization Symposium (LAGOS11)

作者： Heggernes, Pinar van't Hof, Pim Leveque, Benjamin Paul, Christophe Univ Bergen Dept Informat N-5020 Bergen Norway Univ Montpellier 2 CNRS LIRMM F-34095 Montpellier 5 France

We study the following two graph modification problems: given a graph G and an integer k, decide whether G can be transformed into a tree or into a path, respectively, using at most k edge contractions. These problems, which we call TREE CONTRACTION and PATH CONTRACTION, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in 0(n + m) and 0(nm) time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Edge contractions Chordal graphs Graph modification problems polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-item Vickrey-English-Dutch auctions

引用

GAMES AND ECONOMIC BEHAVIOR 2013年第1期81卷 116-129页

作者： Andersson, Tommy Erlanson, Albin Lund Univ Dept Econ SE-22207 Lund Sweden

Assuming that bidders wish to acquire at most one item, this paper defines a polynomial time multi-item auction that locates the VCG prices in a finite number of iterations for any given starting prices. This auction is called the Vickrey-English-Dutch auction and it contains the Vickrey-English auction [Sankaran, J.K., 1994. On a dynamic auction mechanism for a bilateral assignment problem. Math. Soc. Sci. 28, 143-150] and the Vickrey-Dutch auction [Mishra, D., Parkes, D., 2009. Multi-item Vickrey-Dutch auctions. Games Econ. Behav. 66, 326-347] as special cases. By means of numerical experiments, it is showed that when the auctioneer knows the bidders' value distributions, the Vickrey-English-Dutch auction is weakly faster than the Vickrey-English auction and the Vickrey-Dutch auction in 89 percent and 99 percent, respectively, of the investigated problems. A greedy version of the Vickrey-English-Dutch auction is demonstrated to perform even better in the simulation studies. (C) 2013 Elsevier Inc. All rights reserved.

关键词： polynomial time algorithms Multi-item auctions Unit-demand bidders Iterations

来源：评论

学校读者我要写书评

暂无评论

Dominating Induced Matching in Some Subclasses of Bipartite Graphs 1

引用

5th International Conference on 5th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Panda, B. S. Chaudhary, Juhi Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

ISBN: (数字)9783030115098

ISBN: (纸本)9783030115098;9783030115081

Given a graph G = (V, E), a set M subset of E is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is same as G[S], the subgraph of G induced by S = {v is an element of V vertical bar v is incident on an edge of M}. An induced matching M in a graph G is dominating if every edge not in M shares exactly one of its endpoints with a matched edge. The dominating induced matching (DIM) problem (also known as Efficient Edge Domination) is a decision problem that asks whether a graph G contains a dominating induced matching or not. This problem is NP-complete for general graphs as well as for bipartite graphs. In this paper, we show that the DIM problem is NP-complete for perfect elimination bipartite graphs and propose polynomial time algorithms for star-convex, triad-convex and circular-convex bipartite graphs which are subclasses of bipartite graphs.

关键词： Matching Dominating induced matching Graph algorithms NP-completeness polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

An Approach for Finding the Efficient Cost Cores on Weighted Split Networks 13

An Approach for Finding the Efficient Cost Cores on Weighted...

引用

13th International Conference on Computers and Their Applications, CATA 1998

作者： Yang, Shin-Jer Dept. of Computer & Information Science Soochow University Taipei Taiwan

ISBN: (纸本)9781618395443

This paper proposes an approach for solving the cost core issues using Min-Max and Min-Average distance measures on weighted split networks. In fact, finding the efficient cores is very essential to a split network. The required tasks are to allocate a set of servers to some nodes that form a path (core), and to provide the services that clients need in a split network SN(V, E). The services provided by any server are assumed here to be identical, but the building costs for each node are different. First, general strategies for the Min-Max distance and the Min-Average distance measures of a core on general networks are previewed. The definitions and properties of split networks are here described. Then, we propose polynomial time algorithms for Min-Max distance measure on weighted split networks. Min-Average measure is approximate to Min-Max measure, but more complicated than that measure on weighted split networks. Based on the proposed model's technique, the general ß-cores (ß = 2, ß ? Z+) are solved in polynomial time with an ? factor, where ? is the number of possible combinations in the case of ß-cores on weighted split networks. © 13th International Conference on Computers and Their Applications 1998, CATA 1998. All rights reserved.

关键词： Min-Average distance cores Min-Max distance cores polynomial time algorithms split networks time complexity

来源：评论

学校读者我要写书评

暂无评论

Vlastnosti intervalových booleovských funkcí

Vlastnosti intervalových booleovských funkcí

引用

作者： Hušek, Radek Charles University of Prague

Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1

关键词： Boolean functions interval functions polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Vlastnosti intervalových booleovských funkcí

Vlastnosti intervalových booleovských funkcí

引用

作者： Hušek, Radek Charles University of Prague

关键词： Boolean functions interval functions polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：