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

Edge-disjoint spanning trees and the number of maximum state circles of a graph

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第4期35卷 997-1008页

作者： Ma, Xiaoli Wu, Baoyindureng Jin, Xian'an Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Xiamen Univ Sch Math Sci Xiamen 361005 Fujian Peoples R China

Motivated by the connection with the genus of unoriented alternating links, Jin et al. (Acta Math Appl Sin Engl Ser, 2015) introduced the number of maximum state circles of a plane graph G, denoted by , and proved that H is a spanning subgraph of , where e(H), c(H) and v(H) denote the size, the number of connected components and the order of H, respectively. In this paper, we show that for any (not necessarily planar) graph G, can be achieved by the spanning subgraph H of G whose each connected component is a maximal subgraph of G with two edge-disjoint spanning trees. Such a spanning subgraph is proved to be unique and we present a polynomial-time algorithm to find such a spanning subgraph for any graph G.

关键词： Spanning trees polynomial-time algorithm State circle Link

来源：评论

学校读者我要写书评

暂无评论

The weighted coloring problem for two graph classes characterized by small forbidden induced structures

引用

DISCRETE APPLIED MATHEMATICS 2018年 247卷 423-432页

作者： Malyshev, D. S. Natl Res Univ Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia

We show that the weighted coloring problem can be solved for {P-5, banner}-free graphs and for {P-5, dart}-free graphs in polynomial time on the sum of vertex weights. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Computational complexity Coloring problem Hereditary class polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Dominating induced matchings in graphs containing no long claw

引用

JOURNAL OF GRAPH THEORY 2018年第1期88卷 18-39页

作者： Hertz, Alain Lozin, Vadim Ries, Bernard Zamaraev, Viktor de Werra, Dominique Polytech Montreal Dept Math & Ind Engn CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Gerad CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Univ Warwick Math Inst Coventry W Midlands England Univ Fribourg Dept Informat Fribourg Switzerland Ecole Polytech Fed Lausanne Inst Math Lausanne Switzerland

An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph G contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present article, we provide a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once.

关键词： dominating induced matching graphs containing no long claw polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial time algorithms and extended formulations for unit commitment problems

引用

IISE TRANSACTIONS 2018年第8期50卷 735-751页

作者： Guan, Yongpei Pan, Kai Zhou, Kezhuo Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

Recently, increasing penetration of renewable energy generation has created challenges for power system operators to perform efficient power generation daily scheduling, due to the intermittent nature of the renewable generation and discrete decisions of each generation unit. Among all aspects to be considered, a unit commitment polytope is fundamental and embedded in the models at different stages of power system planning and operations. In this article, we focus on deriving polynomial-time algorithms for the unit commitment problems with a general convex cost function and piecewise linear cost function, respectively. We refine an O(T-3) time, where T represents the number of time periods, algorithm for the deterministic single-generator unit commitment problem with a general convex cost function and accordingly develop an extended formulation in a higher-dimensional space that can provide an integral solution, in which the physical meanings of the decision variables are described. This means the original problem can be solved as a convex program instead of a mixed-integer convex program. Furthermore, for the case in which the cost function is piecewise linear, by exploring the optimality conditions, we derive more efficient algorithms for both deterministic (i.e., O(T) time) and stochastic (i.e., O(N) time, where N represents the number of nodes in the stochastic scenario tree) single-generator unit commitment problems. We also develop the corresponding extended formulations for both deterministic and stochastic single-generator unit commitment problems that solve the originalmixed-integer linear programs as linear programs. Similarly, physical meanings of the decision variables are explored to show the insights of the new modeling approach.

关键词： Unit commitment polynomial-time algorithm integral formulation

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Checking Some Properties of Boolean Functions Given by polynomials

引用

THEORY OF COMPUTING SYSTEMS 2016年第3期58卷 383-391页

作者： Selezneva, Svetlana N. Bukhman, Anton V. Moscow MV Lomonosov State Univ Fac Computat Math & Cybernet Moscow Russia

In this paper, we show that checking some properties of Boolean functions which are given by the lists of monomials in their polynomial representations can be implemented in polynomial time. Multi-linear polynomials over GF(2) are often a convenient way to represent Boolean functions. There is a single polynomial for each Boolean function, and the length of the polynomial (i.e. the number of its monomials) which represents a function of n variables can be far less than 2(n). Therefore, in some cases, polynomials are a compressed description of Boolean functions. Besides, polynomial representations of Boolean functions have applications in circuit lower bounds, computational learning, error-correcting codes, cryptography. We construct polynomial-time algorithms for checking some properties of Boolean functions which are given by the lists of monomials in their polynomial representations. The considered properties are self-anti-duality (evenness), self-duality, periodicity, 1-invariance (Mobius transform invariance, coincidence). Note that checking each of these properties directly by definition gives, in the general case, only exponential-time algorithms. The approach to construct our algorithms is the following. Firstly, we prove that if a Boolean function has a certain property then its polynomial has a special structure. And secondly, we check the property by its characterization, cutting negative cases by proven facts. More precisely, we analyze an exponential time algorithm and prove that if the number of steps of the algorithm exceeds a bound, which is polynomial in the input size, and may be computed in advance, then the input will be necessarily rejected.

关键词： Boolean function polynomial representation List of monomials Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 37-45页

作者： Konagaya, Matsuo Otachi, Yota Uehara, Ryuhei Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan

Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time. In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Subgraph isomorphism Graph class polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Finding a cycle base of a permutation group in polynomial time

引用

JOURNAL OF ALGEBRA 2018年 510卷 542-561页

作者： Muzychuk, Mikhail Ponomarenko, Ilia Ben Gurion Univ Negev Beer Sheva Israel Steklov Inst Math St Petersburg St Petersburg Russia

A cycle base of a permutation group is defined to be a maximal set of its pairwise non-conjugate regular cyclic subgroups. It is proved in this paper that a cycle base of a permutation group of degree n can be constru... 详细信息

关键词： Cayley object Cycle base Automorphism group Canonical labeling polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Alphabet Size Reduction for Secure Network Coding: A Graph Theoretic Approach

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第6期64卷 4513-4529页

作者： Guang, Xuan Yeung, Raymond W. Nankai Univ Sch Math Sci Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China Chinese Univ Hong Kong Inst Network Coding Hong Kong Hong Kong Peoples R China

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound.

关键词： Secure network coding information-theoretic security alphabet size graph theory primary minimum cut lower bound polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Characterising Chordal Contact B₀-VPG Graphs 1

引用

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Bonomo, Flavia Pia Mazzoleni, Maria Leonardo Rean, Mariano Ries, Bernard Univ Buenos Aires Dept Computac Fac Ciencias Exactas & Nat Buenos Aires DF Argentina Univ Buenos Aires CONICET Inst Invest Ciencias Computac ICC Buenos Aires DF Argentina Univ Nacl La Plata Dept Matemat Fac Ciencias Exactas La Plata Buenos Aires Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Fribourg Fribourg Switzerland

ISBN: (数字)9783319961514

ISBN: (纸本)9783319961514;9783319961507

A graph G is a B-0-VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact B-0-VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B-0-VPG graphs within the class of chordal graphs and provide a polynomial-time algorithm for recognising these graphs.

关键词： Vertex intersection graphs Contact B-0-VPG graphs Forbidden induced subgraphs Chordal graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for k-Domination and Total k-Domination in Proper Interval Graphs 5th

Improved Algorithms for <i>k</i>-Domination and Total <i>k</...

引用

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Chiarelli, Nina Hartinger, Tatiana Romina Alejandra Leoni, Valeria Lopez Pujato, Maria Ines Milanic, Martin Univ Primorska FAMNIT Glagoljaska 8 Koper 6000 Slovenia Univ Primorska IAM Muzejski Trg 2 Koper 6000 Slovenia Univ Nacl Rosario FCEIA Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina ANPCyT Buenos Aires DF Argentina

ISBN: (纸本)9783319961514;9783319961507

Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set, also known as a k-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, resp. total k-dominating set, in a given graph, are referred to as k-domination, resp. total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from recent work by Kang et al. (2017) that these two families of problems are solvable in time O(vertical bar V(G)vertical bar(6k+4)) in the class of interval graphs. In this work, we develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs. The algorithms run in time O(vertical bar V(G)vertical bar(3k)) for each fixed k >= 1 and are also applicable to the weighted case.

关键词： k-domination Total k-domination Proper interval graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：