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

Grundy coloring in some subclasses of bipartite graphs and their complements

INFORMATION PROCESSING LETTERS 2020年 163卷 105999-105999页

作者： Verma, Shaily Panda, B. S. Indian Inst Technol Delhi New Delhi 110016 India

A vertex v is a Grundy vertex with respect to a proper k-coloring c of a graph G = (V, E) if v has a neighbor of color j for every j (1 = k. The Grundy number decision problem is known to be NP-complete for bipartite ... 详细信息

A vertex v is a Grundy vertex with respect to a proper k-coloring c of a graph G = (V, E) if v has a neighbor of color j for every j (1 <= j < i <= k), where i = c(v). A proper k -coloring c of G is called a Grundy k-coloring of G if every vertex is a Grundy vertex with respect to c and the largest integer k such that G admits a Grundy k-coloring is called the Grundy number of G which is denoted as Gamma(G). Given a graph G and an integer k, the Grundy number decision problem is to decide whether Gamma(G) >= k. The Grundy number decision problem is known to be NP-complete for bipartite graphs and complement of bipartite graphs. In this paper, we strengthen this result by showing that this problem remains NP-complete for perfect elimination bipartite graphs as well as for complement of perfect elimination bipartite graphs. Further, we give a linear-time algorithm to find the Grundy number of chain graphs, which is a proper subclass of the class of perfect elimination bipartite graphs. We also give a linear-time algorithm to find the Grundy number in complements of chain graphs. A partial Grundy coloring of a graph G is a proper k-coloring of G such that there is at least one Grundy vertex with each color i <= 1 < i <= k and the partial Grundy number of G, partial derivative Gamma yy(G), is the largest integer k such that G admits a partial Grundy k-coloring. Given a graph G and an integer k, the partial Grundy number decision problem is to decide whether partial derivative Gamma(G)>= k. It is known that the partial Grundy number decision problem is NP-complete for bipartite graphs. In this paper, we prove that this problem is NP-complete in the complements of bipartite graphs by showing that the Grundy number and partial Grundy number are equal in complements of bipartite graphs. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Grundy coloring Partial Grundy coloring NP-completeness polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP

引用

ALGORITHMICA 2019年第2期81卷 541-556页

作者： Brand, Cornelius Dell, Holger Roth, Marc Saarland Univ D-66123 Saarbrucken Germany Cluster Excellence MMCI D-66123 Saarbrucken Germany

Jaeger et al. (Math Proc Camb Philos Soc 108(1): 35-53, 1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: the evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlen (in: ICALP 2010, vol. 6198, pp. 426-437, Springer, Berlin, Heidelberg, 2010) and Husfeldt and Taslaman (in: IPEC 2010, vol. 6478, pp. 192-203, Springer, Berlin, Heidelberg, 2010) in combination with the results of Curticapean (in: ICALP 2015, pp. 380-392, Springer, 2015), extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y = 1, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time exp(o(n)) unless #ETH fails. Another dichotomy theorem we strengthen is the one of Creignou and Hermann (Inf Comput 125(1): 1-12, 1996) for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that the #P-hard cases cannot be solved in time exp(o(n)) unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp (o(n)) unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean and transfer it to systems of linear equations that might not directly correspond to interpolation.

关键词： ZENO'S paradoxes FIXED point theory COMPLEXITY (Philosophy) polynomial time algorithms LINEAR equations

来源：评论

学校读者我要写书评

暂无评论

Negotiation as concurrency primitive

引用

ACTA INFORMATICA 2019年第2期56卷 93-159页

作者： Desel, Joerg Esparza, Javier Hoffmann, Philipp Fernuniv Hagen Germany Tech Univ Munich Munich Germany

This paper introduces negotiations, a model of concurrency close to Petri nets, with multi-party negotiations as concurrency primitive. We study two fundamental analysis problems. The soundness problem consists in deciding if it is always possible for a negotiation to terminate successfully, whatever the current state is. Given a sound negotiation, the summarization problem aims at computing an equivalent one-step negotiation with the same input/output behavior. The soundness and summarization problems can be solved by means of simple algorithms acting on the state space of the negotiation, which however face the well-known state explosion problem. We study alternative algorithms that avoid the construction of the state space. In particular, we define reduction rules that simplify a negotiation while preserving the sound/non-sound character of the negotiation and its summary. In a first result we show that our rules are complete for the class of weakly deterministic acyclic negotiations, meaning that they reduce all sound negotiations in this class, and only them, to equivalent one-step negotiations. This provides algorithms for both the soundness and the summarization problem that avoid the construction of the state space. We then study the class of deterministic negotiations. Our second main result shows that the rules are also complete for this class, even if the negotiations contain cycles. Moreover, we present an algorithm that completely reduces all sound deterministic negotiations, and only them, in polynomial time.

关键词： NEGOTIATION INVESTMENT analysis TRANSFORMATIONS (Mathematics) polynomial time algorithms PLEONASM

来源：评论

学校读者我要写书评

暂无评论

On partial Grundy coloring of bipartite graphs and chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 271卷 171-183页

作者： Panda, B. S. Verma, Shaily Indian Inst Technol Delhi Dept Math New Delhi 110016 India

A proper k-coloring with colors 1, 2,..., k of a graph G = (V, E) is an ordered partition (V-1, V-2,, V-k) of V such that V, is an independent set or color class in which each vertex v is an element of V-i is assigned color i for 1 <= i <= k. A vertex v is an element of V-i is a Grundy vertex if it is adjacent to at least one vertex in each color class V-j, for every j, j < i. A proper coloring is a partial Grundy coloring if every color class has at least one Grundy vertex in it and the partial Grundy number, denoted as partial derivative Gamma(G), is the maximum number of colors used in a partial Grundy coloring. Given a graph G and an integer k, 1 <= k <= n, the PARTIAL GRUNDY NUMBER DECISION PROBLEM iS LO decide whether partial derivative Gamma(G) >= k. We prove a new upper bound for the partial Grundy number of a graph and show that this upper bound is sharper than the existing upper bound in the literature. It is known that PARTIAL GRUNDY NUMBER DECISION PROBLEM IS NP-complete for the class of bipartite graphs. We strengthen this result by showing that the problem remains NP-complete even for perfect elimination bipartite graphs and star-convex bipartite graphs, two proper subclasses of the class of bipartite graphs. On the positive side, we give a linear time algorithm to determine the partial Grundy number of a chain graph. It is also known that PARTIAL GRUNDY NUMBER DECISION PROBLEM IS NP-complete for the class of chordal graphs. We strengthen this result by showing that the problem remains NP-complete even for doubly chordal graphs, a proper subclass of the class of chordal graphs. On the positive side, we give linear time algorithms to determine the partial Grundy number of split graphs and block graphs, two important subclasses of the class of chordal graphs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Partial Grundy coloring Perfect elimination bipartite graphs Star-convex bipartite graphs Chordal graphs NP-completeness polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms to Augment the Edge-Connectivity of Specified Vertices by One in a Graph

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2019年第2期E102A卷 379-388页

作者： Taoka, Satoshi Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by "Given a graph G = (V, E) and a subset Gamma subset of V, find a minimum set E' of edges such that G' = (V, E boolean OR E') has at least k edge-disjoint paths between any pair of vertices in Gamma." Let sigma be the edge-connectivity of Gamma (that is, G has at least sigma edge-disjoint paths between any pair of vertices in). We propose an algorithm for (sigma+1) ECA-SV which is done in O(vertical bar Gamma vertical bar) maximum flow operations. Then the time complexity is O(sigma(2)vertical bar Gamma vertical bar vertical bar V vertical bar + vertical bar E vertical bar) if a given graph is sparse, or O(vertical bar Gamma parallel to V parallel to B-G vertical bar log(vertical bar V vertical bar(2)/vertical bar B-G vertical bar) + vertical bar E vertical bar) if dense, where vertical bar B-G vertical bar is the number of pairs of adjacent vertices in G. Also mentioned is an O(vertical bar V parallel to E vertical bar + vertical bar V vertical bar(2) log vertical bar V vertical bar) time algorithm for a special case where sigma is equal to the edge-connectivity of G and an O(vertical bar V vertical bar + vertical bar E vertical bar) time one for sigma <= 2.

关键词： graphs connectivity augmentation edge-connectivity edge-interchange operations polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for ridesharing of personal vehicles

引用

THEORETICAL COMPUTER SCIENCE 2019年 788卷 79-94页

作者： 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

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

来源：评论

学校读者我要写书评

暂无评论

Two-machine flowshop scheduling problem with coupled-operations

引用

ANNALS OF OPERATIONS RESEARCH 2019年第2期275卷 511-530页

作者： Meziani, Nadjat Oulamara, Ammar Boudhar, Mourad Abderrahmane Mira Univ Bejaia Algeria Univ Lorraine UMR CNRS 75003 LORIA Lab Campus Sci615 Rue Jardin Bot F-54506 Vandoeuvre Les Nancy France USTHB Fac Math RECITS Lab BP 32 Algiers 16111 Algeria

This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.

关键词： Flowshop Coupled-operations Complexity polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

关键词： Ridesharing problem Optimization problems polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Reduction of Constraints from Multipartition to Bipartition in Augmenting Edge-Connectivity of a Graph by One

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第2期E101A卷 357-366页

作者： Taoka, Satoshi Oki, Tadachika Mashima, Toshiya Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hiroshima Int Univ Fac Infrastractural Technol Dept Informat Technol Kure 7370112 Japan

The k-edge-connectivity augmentation problem with multipartition constraints (kECAMP, for short) is defined by "Given a multi-graph G = (V, E) and a multipartition pi = { V-1, ... ,V-r} (r >= 2) of V, that is, V = U-h(r) V-h= 1 V-h and V-i boolean AND V-j = phi (1 <= i < j <= r), find an edge set E-f of minimum\cardinality, consisting of edges that connect V-i and V-j (i not equal j), such that (V;E boolean OR E-f) is k-edge-connected, where a multigraph means a graph, with unweighted edges, such that multiple edges may exist." The problem has applications for constructing a fault-tolerant network under building constraints, and so on. In this paper, we give a linear time reduction of (sigma + 1) ECAMP with vertical bar pi vertical bar >= 3 to (sigma + 1) ECAMP with vertical bar pi vertical bar = 2 when the edge-connectivity of G is sigma and a structural graph F(G) of G is given.

关键词： connectivity augmentation problems edge-connectivity multi-partition constraints graphs polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：