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

Independent domination in finitely defined classes of graphs: polynomial algorithms

DISCRETE APPLIED MATHEMATICS 2015年 182卷 2-14页

作者： Lozin, Vadim Mosca, Raffaele Purcell, Christopher Univ Warwick Inst Math Coventry CV4 7AL W Midlands England Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

We study the problem of finding in a graph an inclusionwise maximal independent set Of minimum cardinality, known as MINIMUM MAXIMAL INDEPENDENT SET or INDEPENDENT DOMINATING SET problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with SATISFIABILITY, the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271-284] reveals various conditions under which the INDEPENDENT DOMINATING SET problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P-2 + P-3-free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P-3 + P-3-free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Independent domination Finitely defined class of graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting Critical Protected Links to Keep Connectivity to Servers Against Link Failures 7

Detecting Critical Protected Links to Keep Connectivity to S...

引用

7th International Conference on New Technologies, Mobility and Security (NTMS)

作者： Irie, Daishi Kurimoto, Shinya Miwa, Hiroyoshi Kwansei Gakuin Univ Sch Sci & Technol 2-1 Gakuen Sanda Hyogo 6691337 Japan

ISBN: (纸本)9781479987849

It is important for service providers to design and operate reliable network which is robust against network failures. Especially, a network must be sufficiently connected, even if link failures occur. It is desirable to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, link protection needs much cost;therefore, it is important to find the smallest number of links to be protected so that a network resulting from failures of any non-protected links provides users connectivity. In this paper, we focus on the criteria that all connected components include specified servers in a resulting network after links fail. Our purpose is to find the links to be protected such that, even if any non-protected links fail, all connected components in the resulting network include the servers. First, we formulate this link protection problem and prove that this problem is NP-hard. Next, we present a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we present a polynomial-time approximation algorithm with the approximation ratio of a constant, the number of the simultaneous link failures. In addition, we apply the approximation algorithms to the topology of actual networks and evaluate the approximation ratio. The results indicate that the approximation ratio in the actual networks is much smaller than the theoretical upper bound. It follows that our algorithms are efficient when we determine protected links in an actual network.

关键词： link protection network design connectivity optimization NP-hard approximation algorithm polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Variants of Graph Matching for Tree-like Graphs

Variants of Graph Matching for Tree-like Graphs

引用

2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity)

作者： Nagoya, Takayuki Tottori Univ Environm Studies Gen Educ Ctr Tottori 6891111 Japan

ISBN: (纸本)9781509018932

Graphs can be effectively used to represent relationships between objects such as social networks, web search engines and genome sequencing. In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the prefix set of graph isomorphism. We propose polynomial-time exact algorithms for these problems on graphs with tree-like structure. These could be useful tools for big data processing.

关键词： graph isomorphism with restriction partial k-trees polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Independent domination in finitely defined classes of graphs: polynomial algorithms

Independent domination in finitely defined classes of graphs...

引用

8th International Colloquium on Graphs and Optimization (GO)

关键词： Independent domination Finitely defined class of graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs

A Polynomial-Time Algorithm for Optimizing over <i>N</i>-Fol...

引用

14th International Conference Integer Programming and Combinatorial Optimization

作者： Hemmecke, Raymond Koeppe, Matthias Weismantel, Robert Tech Univ Munich D-8000 Munich Germany Univ Calif Davis CA USA ETH Zurich Switzerland

ISBN: (纸本)9783642130359

In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

关键词： N-fold integer programs Graver basis augmentation algorithm polynomial-time algorithm stochastic multi-commodity flow stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

Maximum Exploratory Equivalence in Trees

Maximum Exploratory Equivalence in Trees

引用

3rd International Conference on Innovative Network Systems and Applications (iNetSApp) held in conjunction with Federated Conference on Computer Science and Information Systems (FedCSIS)

作者： Furst, Luka Cibej, Uros Mihelic, Jurij Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 SI-1000 Ljubljana Slovenia

ISBN: (纸本)9788360810668

Many practical problems are modeled with networks and graphs. Their exploration is of significant importance, and several graph-exploration algorithms already exist. In this paper, we focus on a type of vertex equivalence, called exploratory equivalence, which has a great potential to speed up such algorithms. It is an equivalence based on graph automorphisms and can, for example, help us in solving the subgraph isomorphism problem, which is a well-known NP-hard problem. In particular, if a given pattern graph has nontrivial automorphisms, then each of its nontrivial exploratory equivalent classes gives rise to a set of constraints to prune the search space of solutions. In the paper, we define the maximum exploratory equivalence problem. We show that the defined problem is at least as hard the graph isomorphism problem. Additionally, we present a polynomial-time algorithm for solving the problem when the input is restricted to tree graphs. Furthermore, we show that for trees, a maximum exploratory equivalent partition leads to a globally optimal set of subgraph isomorphism constraints, whereas this is not necessarily the case for general graphs.

关键词： computational complexity search problems trees (mathematics) NP-hard problem general graphs graph automorphisms graph-exploration algorithms maximum exploratory equivalence problem nontrivial automorphisms polynomial-time algorithm search space subgraph isomorphism constraints tree graphs vertex equivalence Computational modeling Computers Data models Partitioning algorithms Search problems Software algorithms Tree graphs

来源：评论

学校读者我要写书评

暂无评论

Optimal Power Control in Two-Tier Networks at Low-SNR Regime 23

Optimal Power Control in Two-Tier Networks at Low-SNR Regime

引用

23nd Signal Processing and Communications Applications Conference (SIU)

作者： Demir, Uygar Toker, Cenk Inaltekin, Hazer Hacettepe Univ Elekt & Elekt Muhendisligi Bolumu Ankara Turkey Antalya Uluslararasi Univ Elekt & Elekt Muhendisligi Bolumu Dosemealti Antalya Turkey

ISBN: (纸本)9781467373869

This paper considers optimum uplink power control policy that maximizes system capacity without any interference cancellation techniques for HetNets or cognitive-radio (CR) networks at low-SNR regime. System model has two-tier to cover cognitive-radio and heterogenous networks structures. Tier 2 users cause interference on tier 1 user under spectrum sharing paradigm. In proposed scenario, this interference power on tier 1 user is limited at a certain level. The objective function of power optimization problem is changed with an upper bound function to find optimum power control policy under individual peak power constraint at Tier2s and total interference constraint at Tierl for uplink case at low-SNR regime. To this end, two optimal solutions, one of which is algoritmic and the other is analytical, have found from two different upper bound approximations. By exploiting analytical solution, a fast and low-complex algorithm is derived. At the end of paper, these two approximations and DC programming algorithm which is well-studied and given well-approximated lower bound have been compared with each other.

关键词： HetNets cognitive-radio networks power control low-SNR regime interference constraint polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the maximum independent set problem in subclasses of subcubic graphs

引用

JOURNAL OF DISCRETE algorithmS 2015年 31卷 104-112页

作者： Lozin, Vadim Monnot, Jerome Ries, Bernard Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England CNRS LAMSADE UMR 7243 F-75700 Paris France Univ Paris 09 PSL F-75775 Paris 16 France

It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for 3-regular Hamiltonian graphs and for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of His a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class. (c) 2014 Elsevier B.V. All rights reserved.

关键词： Independent set polynomial-time algorithm Subcubic graph APX-completeness

来源：评论

学校读者我要写书评

暂无评论

MATCHING PROBLEMS WITH DELTA-MATROID CONSTRAINTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第2期28卷 942-961页

作者： Kakimura, Naonori Takamatsu, Mizuyo Univ Tokyo Coll Arts & Sci Tokyo 1538902 Japan Chuo Univ Dept Informat & Syst Engn Tokyo 1128551 Japan

Given an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid matching problem is to find a maximum cardinality matching M such that the set of the end vertices of M belongs to F. This problem is a natural generalization of the matroid matching problem to delta-matroids, and thus it cannot be solved in polynomial time in general. This paper introduces a class of the delta-matroid matching problem, where the given delta-matroid is a projection of a linear delta-matroid. We first show that it can be solved in polynomial time if the given linear delta-matroid is generic. This result enlarges a polynomially solvable class of matching problems with precedence constraints on vertices such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

关键词： constrained matching delta-matroid polynomial-time algorithm mixed matrix theory

来源：评论

学校读者我要写书评

暂无评论

Optimal shift coloring of trees

引用

OPERATIONS RESEARCH LETTERS 2014年第4期42卷 251-256页

作者： Andreatta, Giovanni De Giovanni, Luigi Serafini, Paolo Univ Padua Dipartimento Matemat I-35121 Padua Italy Univ Udine Dipartimento Matemat & Informat I-33100 Udine Italy

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph coloring Shift coloring Trees polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：