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

algorithmic aspects of b-disjunctive domination in graphs

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期36卷 572-590页

作者： Panda, B. S. Pandey, Arti Paul, S. Indian Inst Technol Delhi Dept Math Hauz Khas New Delhi 110016 India Indian Inst Technol Ropar Dept Math Rupnagar 140001 Punjab India Indian Inst Informat Technol Guwahati Dept Comp Sci & Engn GN Bordoloi Rd Gauhati 781001 India

For a fixed integer , a set is called a b-disjunctive dominating set of the graph if for every vertex , v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by . Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, is equal to , the domination number of G for and observe that need not be equal to for . We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for . Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a -approximation algorithm for MbDDP, where is the maximum degree of input graph and prove that MbDDP cannot be approximated within for any unless NP DTIME. Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree .

关键词： Domination Chordal graph graph algorithm Approximation algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Data dependent circuit for subgraph isomorphism problem

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2003年第5期E86D卷 796-802页

作者： Ichikawa, S Yamamoto, S Toyohashi Univ Technol Dept Knowledge Based Informat Toyohashi Aichi 4418580 Japan

Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

关键词： NP-complete custom circuit FPGA graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Hardness Results of Connected Power Domination for Bipartite graphs and Chordal graphs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第6期35卷 669-703页

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

A set D subset of V of a graph G = (V, E) is called a connected power dominating set of G if G[D], the subgraph induced by D, is connected and every vertex in the graph can be observed from D, following the two observation rules for power system monitoring: Rule 1: if v epsilon D, then v can observe itself and all its neighbors, and Rule 2: for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G, Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be NP-complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains NP-complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292{315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1- epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P = NP, for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX-hard for bounded degree graphs.

关键词： Domination connected power domination polynomial-time algorithm NP-complete graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A TECHNIQUE FOR EXACT COMPUTATION OF PRECOLORING EXTENSION ON INTERVAL graphS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2013年第1期24卷 109-122页

作者： Ehmsen, Martin R. Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

Inspired by a real life application, we investigate the computationally hard problem of extending a precoloring of an interval graph to a proper coloring under some bound on the number of available colors. We are interested in quickly determining whether or not such an extension exists on instances occurring in practice in connection with campsite bookings on a campground. A naive exhaustive search does not terminate in reasonable time. We have formulated a new approach which moves the computation time within I he usable range on all the data samples available to us.

关键词： graph algorithm interval graphs graph coloring

来源：评论

学校读者我要写书评

暂无评论

The toughness of split graphs

引用

DISCRETE MATHEMATICS 1998年第1-3期190卷 295-297页

作者： Woeginger, GJ Graz Tech Univ Inst Math B A-8010 Graz Austria

In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231-245). (C) 1998 Elsevi... 详细信息

关键词： graph algorithm split graph toughness Hamiltonian cycle

来源：评论

学校读者我要写书评

暂无评论

PARALLEL (DELTA+1)-COLORING OF CONSTANT-DEGREE graphS

引用

INFORMATION PROCESSING LETTERS 1987年第4期25卷 241-245页

作者： GOLDBERG, AV PLOTKIN, SA Laboratory for Computer Science Massachusetts Institute of Technology Cambridge MA 02139 U.S.A.

This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of Δ using Δ + 1 colors and for finding a maximal independent set in a constant-degree graph. Given a graph with n vertices, the algorithms run in O(lg∗n) time on an EREW PRAM with O(n) processors. The algorithms use only local communication and achieve the same complexity bounds when implemented in a distributed model of parallel computation.

关键词： Parallel algorithm graph algorithm graph coloring maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Combine and conquer

引用

algorithmICA 1997年第3期18卷 324-362页

作者： Cohen, RF Tamassia, R BROWN UNIV DEPT COMP SCI PROVIDENCE RI 02912 USA

We present a general technique for dynamizing a class of problems whose underlying structure is a computation graph embedded in a tree. We introduce three fully dynamic data structures, called path attribute systems, tree attribute systems, and linear attribute grammars, which extend and generalize the dynamic trees of Sleator and Tarjan. More specifically, we associate values, called attributes, with the nodes and paths of a rooted tree. Path attributes form a path attribute system if they can be maintained in constant rime under path concatenation. Node attributes form a tree attribute system if the tree attributes of the tail of a path II can be determined in constant time from the path attributes of II. A linear attribute grammar is a tree-based linear expression such that the values of a node It art calculated from the values at the parent, siblings, and/or children of it. We provide a framework for maintaining path attribute systems, tree attribute systems, and linear attribute grammars in a fully dynamic environment using linear space and logarithmic time per operation. Also, we demonstrate the applicability of our techniques by showing examples of graph and geometric problems that can be efficiently dynamized, including biconnectivity and triconnectivity queries, planarity testing, drawing trees and series-parallel digraphs, slicing floorplan compaction, point location, and many optimization problems on bounded tree-width graphs.

关键词： dynamic algorithm data structure tree attribute grammar arithmetic expression point location graph algorithm

来源：评论

学校读者我要写书评

暂无评论

AN INCREMENTAL LINEAR-TIME algorithm FOR RECOGNIZING INTERVAL-graphS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1989年第1期18卷 68-81页; 作者： KORTE, N MOHRING, RH TECH UNIV BERLIN FACHBEREICH MATH MA61 D-1000 BERLIN 12 FED REP GER; The fastest-known algorithm for recognizing interval graphs [S. Booth and S. Lucker, J. Comput. System Sci., 13 (1976), pp. 335–379] iteratively manipulates the system of all maximal cliques of the given graph in a r... 详细信息; The fastest-known algorithm for recognizing interval graphs [S. Booth and S. Lucker, J. Comput. System Sci., 13 (1976), pp. 335–379] iteratively manipulates the system of all maximal cliques of the given graph in a rather complicated way in order to construct a consecutive arrangement (more precisely, a tree representation of all possible consecutive arrangements). This paper presents a much simpler algorithm using a related, but much more informative tree representation of interval graphs. This tree is constructed in an incremental fashion by adding vertices to the graph in a predefined order such that adding a vertex u takes $O (| Adj (u) | + 1)$; 关键词： 68C25 68E10 interval graphs incremental recognition graph algorithm perfect elimination scheme modified PQ-tree amortized time; 来源：评论; 学校读者我要写书评

暂无评论

Maximum weight induced matching in some subclasses of bipartite graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期40卷 713-732页

作者： Panda, B. S. Pandey, Arti Chaudhary, Juhi Dane, Piyush Kashyap, Manav Indian Inst Technol Delhi Dept Math New Delhi 110016 India Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

A subset M subset of E of edges of a graph G=(V,E) is called amatchinginGif no two edges inMshare a common vertex. A matchingMinGis called aninduced matchingifG[M], the subgraph ofGinduced byM, is the same asG[S], the subgraph ofGinduced byS={v is an element of V|vertical bar v}vis incident on an edge ofM}. TheMaximum Induced Matchingproblem is to find an induced matching of maximum cardinality. Given a graphGand a positive integerk, theInduced Matching Decisionproblem is to decide whetherGhas an induced matching of cardinality at leastk. TheMaximum Weight Induced Matchingproblem in a weighted graph G = (V,E) in which the weight of each edge is a positive real number, is to find an induced matching such that the sum of the weights of its edges is maximum. It is known that theInduced Matching Decisionproblem and hence theMaximum Weight Induced Matchingproblem is known to be NP-complete for general graphs and bipartite graphs. In this paper, we strengthened this result by showing that theInduced Matching Decisionproblem is NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs, the subclasses of the class of bipartite graphs. On the positive side, we propose polynomial time algorithms for theMaximum Weight Induced Matchingproblem for circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial time reductions from theMaximum Weight Induced Matchingproblem in these graph classes to theMaximum Weight Induced Matchingproblem in convex bipartite graphs.

关键词： Matching Induced matching Bipartite graphs graph algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Higher-Order Truss Decomposition in graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第4期35卷 3966-3978页

作者： Chen, Zi Yuan, Long Han, Li Qian, Zhengping East China Normal Univ Software Engn Inst Shanghai 200050 Peoples R China Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Jiangsu Peoples R China Alibaba Grp Hangzhou 310052 Peoples R China

kappa-truss model is a typical cohesive subgraph model and has been received considerable attention recently. However, the k-truss model only considers the direct common neighbors of an edge, which restricts its ability to reveal fine-grained structure information of the graph. Motivated by this, in this paper, we propose a new model named (k, tau)-truss that considers the higher-order neighborhood (tau hop) information of an edge. Based on the (k, tau)-truss model, we study the higher-order truss decomposition problem which computes the (k, tau)-trusses for all possible k values regarding a given tau. Higher-order truss decomposition can be used in the applications such as community detection and search, hierarchical structure analysis, and graph visualization. To address this problem, we first propose a bottom-up decomposition paradigm in the increasing order of k values to compute the corresponding (k,tau)-truss. Based on the bottom-up decomposition paradigm, we further devise three optimization strategies to reduce the unnecessary computation. We evaluate our proposed algorithms on real datasets and synthetic datasets, the experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

关键词： Computational modeling Image edge detection Optimization Scalability Data models Collaboration Visualization Higher-order neighborhood truss decomposition graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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