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

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

来源：评论

学校读者我要写书评

暂无评论

Emergency Connectivity in Ad-hoc Networks with Selfish Nodes

引用

ALGORITHMICA 2014年第2期68卷 358-389页

作者： Karakostas, George Markou, Euripides McMaster Univ Sch Computat Engn & Sci Dept Comp & Software Hamilton ON L8S 4K1 Canada Univ Cent Greece Dept Comp Sci & Biomed Informat Lamia 35100 Greece

Inspired by the CONFIDANT protocol (Buchegger and Boudec in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 226-236, 2002), we define and study a basic reputation-based protocol in multihop wireless networks with selfish nodes. Its reputation mechanism is implemented through the ability of any node to define a threshold of tolerance for any of its neighbors, and to cut the connection to any of these neighbors that refuse to forward an amount of flow above that threshold. The main question we would like to address is whether one can set the initial conditions so that the system reaches an equilibrium state where a non-zero amount of every commodity is routed. This is important in emergency situations, where all nodes need to be able to communicate even with a small bandwidth. Following a standard approach, we model this protocol as a game, and we give necessary and sufficient conditions for the existence of non-trivial Nash equilibria. Then we enhance these conditions with extra conditions that give a set of necessary and sufficient conditions for the existence of connected Nash equilibria. We note that it is not always necessary for all the flow originating at a node to reach its destination at equilibrium. For example, a node may be using unsuccessful flow in order to effect changes in a distant part of the network that will prove quite beneficial to it. We show that we can decide in polynomial time whether there exists a (connected) equilibrium without unsuccessful flows. In that case we calculate (in polynomial time) initial values that impose such an equilibrium on the network. On the negative side, we prove that it is NP-hard to decide whether a connected equilibrium exists in general (i.e., with some nodes using unsuccessful flows at equilibrium).

关键词： AD hoc networks (Computer networks) polynomial time algorithms EQUILIBRIUM statistical mechanics BANDWIDTHS NASH equilibrium

来源：评论

学校读者我要写书评

暂无评论

The Inverse 1-Median Problem on Tree Networks with Variable Real Edge Lengths

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-6页

作者： Wu, Longshu Lee, Joonwhoan Zhang, Jianhua Wang, Qin China Jiliang Univ Coll Sci Hangzhou 310018 Zhejiang Peoples R China Chonbuk Natl Univ Div Comp Sci & Engn Jeonju 561756 Jeonbuk South Korea Zhejiang Univ Technol Coll Comp Sci Hangzhou 310023 Zhejiang Peoples R China

Location problems exist in the real world and they mainly deal with finding optimal locations for facilities in a network, such as net servers, hospitals, and shopping centers. The inverse location problem is also often met in practice and has been intensively investigated in the literature. As a typical inverse location problem, the inverse 1-median problem on tree networks with variable real edge lengths is discussed in this paper, which is to modify the edge lengths at minimum total cost such that a given vertex becomes a 1-median of the tree network with respect to the new edge lengths. First, this problem is shown to be solvable in linear time with variable nonnegative edge lengths. For the case when negative edge lengths are allowable, the NP-hardness is proved under Hamming distance, and strongly polynomial time algorithms are presented under l(1) and l(infinity) norms, respectively.

关键词： INVERSE problems (Differential equations) TREE graphs COMPUTER networks VARIABLES (Mathematics) LOCATION problems (Programming) polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Qualitative analysis of concurrent mean-payoff games

引用

INFORMATION AND COMPUTATION 2015年 242卷 2-24页

作者： Chatterjee, Krishnendu Ibsen-Jensen, Rasmus IST Austria Klosterneuburg Austria

We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it;or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies;(2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players;and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imp

关键词： FINITE state machines (Computer science) GRAPH theory QUALITATIVE research COMPUTATIONAL complexity PROBABILITY theory polynomial time algorithms GAME theory

来源：评论

学校读者我要写书评

暂无评论

Topological morphing of planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2013年 514卷 2-20页

作者： Angelini, Patrizio Cortese, Pier Francesco Di Battista, Giuseppe Patrignani, Maurizio Roma Tre Univ Dipartimento Informat & Automaz Rome Italy

In this paper we analyze the relationships among different planar embeddings of the same graph and study how two planar embeddings can be morphed one into the other with the minimum number of elementary changes, while preserving the mental map of the user. We call this problem Topological Morphing, in analogy with the well-known Geometric Morphing problem, in which it is studied how two planar drawings can be morphed one into the other with the minimum number of elementary changes. First, we define two operations, called flip and skip, describing natural transformations of a graph embedding that preserve the mental map of the user. Then, we study the problem of performing a morph while minimizing the number of these operations. We show that the Topological Morphing problem is NP-hard for biconnected planar graphs, we give polynomial-time algorithms for some restricted versions of the problem, and, based on such polynomial-time algorithms, we give a fixed-parameter tractable algorithm for the general case. (C) 2013 Elsevier B.V. All rights reserved.

关键词： MORPHING (Computer animation) PLANAR graphs TOPOLOGICAL embeddings COMPUTER users PARAMETER estimation polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bounded monotone recursion and multihead automata

引用

PROGRAMMING AND COMPUTER SOFTWARE 2013年第6期39卷 301-308页

作者： Marchenkov, S. S. Moscow MV Lomonosov State Univ Fac Computat Math & Cybernet Moscow 119991 Russia

On the basis of bounded monotone recursion, a class BMR of word functions over the alphabet {1, 2} is defined. A new type of a computing device is introduced, which is called a multihead nonerasing automaton with output, or an MH automaton. It is proved that the class BMR coincides with the class MHA of word functions computable by MH automata in polynomial time. Numerous examples of word functions from the class BMR are given.

关键词： MONOTONE operators RECURSION theory MACHINE theory polynomial time algorithms SUMMABILITY theory

来源：评论

学校读者我要写书评

暂无评论

On the discrete logarithm problem

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2014年第1期24卷 45-52页

作者： Stepanov, Sergei A. Inst Informat Transmiss Problems RAS Moscow Russia

Let F-q be a finite field of characteristic p with q = p(v) elements, g a primitive element, a not equal 0 an arbitrary element of F-q, and x = log g a the discrete logarithm of a to the base g. In this paper we consider the discrete logarithm problem in the case when q equivalent to 1( mod 4) and put forward a deterministic algorithm computing the first k <= c log n digits x(0), x(1),..., x(k), k < n, in the binary expansion x = x(0) + x(1)2+ x(2)2(2) + - - - + x(n)2(n) of x in a polynomial time.

关键词： LOGARITHMS FINITE fields (Algebra) DETERMINISTIC algorithms polynomial time algorithms BINARY system (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

2-edge-Hamiltonian-connectedness of 4-connected plane graphs

引用

EUROPEAN JOURNAL OF COMBINATORICS 2014年 35卷 432-448页

作者： Ozeki, Kenta Vrana, Petr Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan ERATO JST Kawarabayashi Large Graph Project Tokyo Japan Univ W Bohemia Dept Math Plzen 30614 Czech Republic Inst Theoret Comp Sci Ctr Excellence ITI Plzen 30614 Czech Republic European Ctr Excellence NTIS New Technol Informat Soc Plzen 30614 Czech Republic

A graph G is called 2-edge-Hamiltonian-connected if for any X subset of {x(1)x(2) : x(1), x(2) is an element of V(G)} with 1 <= vertical bar X vertical bar <= 2, G boolean OR X has a Hamiltonian cycle containing all edges in X, where G boolean OR X is the graph obtained from G by adding all edges in X. In this paper, we show that every 4-connected plane graph is 2-edge-Hamiltonian-connected. This result is best possible in many senses and an extension of several known results on Hamiltonicity of 4-connected plane graphs, for example, Tutte's result saying that every 4-connected plane graph is Hamiltonian, and Thomassen's result saying that every 4-connected plane graph is Hamiltonian-connected. We also show that although the problem of deciding whether a given graph is 2-edge-Hamiltonian-connected is NP-complete, there exists a polynomial time algorithm to solve the problem if we restrict the input to plane graphs. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： HAMILTONIAN systems CONNECTEDNESS (Mathematics) GRAPH connectivity PATHS & cycles (Graph theory) PROBLEM solving polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

GENERATING RANDOM FACTORED GAUSSIAN INTEGERS, EASILY

引用

MATHEMATICS OF COMPUTATION 2015年第297期85卷 503-516页

作者： Lebowitz-Lockard, Noah Pomerance, Carl Emory Univ Dept Math & Comp Sci Atlanta GA 30307 USA Dartmouth Coll Dept Math Hanover NH 03755 USA

We present a (random) polynomial-time algorithm to generate a random Gaussian integer with the uniform distribution among those with norm at most N, along with its prime factorization. The method generalizes to finding a random ideal in the ring of integers of a quadratic number field together with its prime ideal factorization. We also discuss the analogous problem for higher degree number fields.

关键词： GAUSSIAN integers polynomial time algorithms UNIFORM distribution (Probability theory) FACTORIZATION (Mathematics) PRIME factors (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling

引用

GEOMETRIC AND FUNCTIONAL ANALYSIS 2018年第1期28卷 100-145页

作者： Garg, Ankit Gurvits, Leonid Oliveira, Rafael Wigderson, Avi Microsoft Res New England Cambridge MA 02142 USA CUNY City Coll Dept Comp Sci New York NY 10031 USA Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Inst Adv Study Olden Lane Princeton NJ 08540 USA

The celebrated Brascamp-Lieb (BL) inequalities [BL76,Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters (which we later define below). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute: (1) Feasibility of BL-datum, (2) Optimal BL-constant, (3) Weak separation oracle for BL-polytopes. What is particularly exciting about this progress, beyond the better understanding of BL-inequalities, is that the objects above naturally encode rich families of optimization problems which had no prior efficient algorithms. In particular, the BL-constants (which we efficiently compute) are solutions to non-convex optimization problems, and the BL-polytopes (for which we provide efficient membership and separation oracles) are linear programs with exponentially many facets. Thus we hope that new combinatorial optimization problems can be solved via reductions to the ones above, and make modest initial steps in exploring this possibility. Our algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by [Gur04]. To obtain the results above, we utilize the two (very recent and different) algorithms for the operator scaling problem [GGOW16,IQS15]. Our reduction implies algorithmic versions of many of the known structural results on BL-inequalities, and in some cases provide proofs that are different or simpler than existing ones. Further, the analytic properties of the [GGOW16] algorithm provide new, effective bounds on the magnitude and continuity of BL-constants;prior work relied on compactness, and thus provided

关键词： AUTOMATIC differentiation MATHEMATICAL optimization INEQUALITIES (Mathematics) algorithms polynomial time algorithms QUANTUM information theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：