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

Closest 4-leaf power is fixed-parameter tractable

DISCRETE APPLIED MATHEMATICS 2008年第18期156卷 3345-3361页

作者： Dom, Michael Guo, Jiong Hueffner, Falk Niedermeier, Rolf Univ Jena Inst Informat D-07743 Jena Germany

The NP-complete CLOSEST 4-LEAF POWER problem asks, given an undirected graph, whether it can be modified by at most r edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree-the 4-leaf root-with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on CLOSEST 2-LEAF POWER and CLOSEST 3-LEAF POWER, we give the first algorithmic result for CLOSEST 4-LEAF POWER, showing that CLOSEST 4-LEAF POWER is fixed-parameter tractable with respect to the parameter r. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Fixed-parameter tractability graph algorithm graph modification graph power Leaf power Forbidden subgraph characterization

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for determining (generalized) core groups in social networks

引用

ADVANCES IN DATA ANALYSIS AND CLASSIFICATION 2011年第2期5卷 129-145页

作者： Batagelj, Vladimir Zaversnik, Matjaz Univ Ljubljana FMF Dept Math Ljubljana 1000 Slovenia

The structure of a large network (graph) can often be revealed by partitioning it into smaller and possibly more dense sub-networks that are easier to handle. One of such decompositions is based on "k-cores", proposed in 1983 by Seidman. Together with connectivity components, cores are one among few concepts that provide efficient decompositions of large graphs and networks. In this paper we propose an efficient algorithm for determining the cores decomposition of a given network with complexity O(m), where m is the number of lines (edges or arcs). In the second part of the paper the classical concept of k-core is generalized in a way that uses a vertex property function instead of degree of a vertex. For local monotone vertex property functions the corresponding generalized cores can be determined in O(***(Delta, log n)) time, where n is the number of vertices and Delta is the maximum degree. Finally the proposed algorithms are illustrated by the analysis of a collaboration network in the field of computational geometry.

关键词： Core Large network Decomposition graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Cohesive Group Nearest Neighbor Queries on Road-Social Networks under Multi-Criteria

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第11期33卷 3520-3536页

作者： Guo, Fangda Yuan, Ye Wang, Guoren Chen, Lei Lian, Xiang Wang, Zimeng Northeastern Univ Sch Comp Sci & Engn Shenyang 110169 Liaoning Peoples R China Beijing Inst Technol Sch Comp Sci & Technol Beijing 100081 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Kent State Univ Dept Comp Sci Kent OH 44242 USA

The group nearest neighbor (GNN) search on a road network G(r), i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on G(r), has been extensively studied;however, previous works neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Meanwhile, the ratings of spatial objects can also be used as recommended guidelines. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study two new problems: (1) a GNN search on a road network that incorporates cohesive social relationships (CGNN) and (2) a CGNN query under multi-criteria (MCGNN). Specifically, both the query users of highest closeness and the corresponding top-j objects are retrieved. To address critical challenges on the effectiveness of results and the efficiency of computation over large road-social networks: (1) for CGNN, we propose a filtering-and-verification framework. During filtering, we prune substantial unpromising users and objects using social and geospatial constraints. During verification, we obtain the object candidates, among which the top j are selected, with respect to the qualified users;(2) for MCGNN, we propose threshold-based selection and expansion strategies, where different strict boundaries are proposed to ensure that correct top-j objects are found early. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions.

关键词： Query processing GNN query k-core graph algorithm road network social network

来源：评论

学校读者我要写书评

暂无评论

On the decomposition of circulant graphs using algorithmic approaches

引用

ALEXANDRIA ENGINEERING JOURNAL 2022年第10期61卷 8263-8275页

作者： El-Mesady, A. Hamed, Y. S. Shabana, H. Menoufia Univ Fac Elect Engn Dept Phys & Engn Math Menoufia 32952 Egypt Taif Univ Coll Sci Dept Math & Stat POB 11099 Taif 21944 Saudi Arabia

Many structural models in chemistry, biology, computer science, sociology, and operations research can be analyzed using graph theory. Some examples of these structure models are species movement between regions, molecular bonds, shortest spanning trees, development of computer algorithms. This paper introduces the edge decomposition of circulant graphs with 2n vertices by different graph classes. These circulant graphs are denoted as C-2n,C-n, where n is the degree of the graph C-2n,C-n. We propose two algorithmic approaches for constructing edge decomposition of C-2n,C-n. With aid of the proposed algorithmic approaches, we construct paths decompositions, trees decompositions, disjoint unions of cycles and trees decompositions, and complete bipartite graphs decompositions of C-2n,C-n. In the end, a recursive construction of an edge decomposition, based on orthogonal edge decompositions, is proposed. This helps in using the mutually orthogonal decompositions of the circulant graphs C2n,n in several applications, such as the design of experiments and binary codes generation. (C) 2022 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Alexandria University.

关键词： Circulant graph Decomposition graph translation graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid method for solving multi-depot VRP with simultaneous pickup and delivery incorporated with Weber basis saving heuristic

引用

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 2016年第1期10卷

作者： Shimizu, Yoshiaki Sakaguchi, Tatsuhiko Yoo, Jae-Kyu Toyohashi Univ Technol Dept Mech Engn 1-1 HibarigaokaTenpaku Cho Toyohashi Aichi 4418580 Japan Kanazawa Univ Sch Econ Kakuma Cho Kanazawa Ishikawa 9201192 Japan

Under growing concerns with sustainability in global and changing market, establishing a cooperative and competitive logistic is becoming a keen issue to provide manufacturing systems amenable to sales and operations planning. As a deployment for such practice, we have engaged in the various studies on logistics optimization. Especially, noticing that transportation cost and/or CO2 emission actually depend not only on distance but also loading weight (Weber basis), we have recently developed a few hybrid meta-heuristic methods for vehicle routing problems (VRP) and shown their effectiveness through numerical experiments. To the best of our knowledge, however, there exist no studies that take the Weber basis into account on VRP except for ours. As a hot interest in this area, we pay our attention on VRP with simultaneous pickup and delivery (VRPSPD). Then, this study attempts to extend the foregoing Weber basis study under single depot to multi-depot problem and intends to reveal some properties of VRPSPD. To work with such concerns, we have developed a novel hierarchical method comprised of a modified tabu search, a graph algorithm for the minimum cost flow problem and a Weber basis saving method. The proposed method is possible to solve various real world applications practically even with large problem sizes. Finally, the effectiveness of the proposed method is validated through numerical experiments taken place from various viewpoints to discuss about some peculiar features of VRPSPD.

关键词： Multi-depot VRPSPD Hybrid approach Weber basis saving method graph algorithm Modified tabu search

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of independent set reconfiguration problems

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 336-345页

作者： Ito, Takehiro Kaminski, Marcin Ono, Hirotaka Suzuki, Akira Uehara, Ryuhei Yamanaka, Katsuhisa Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Univ Warsaw Dept Math Comp Sci & Mech Banacha 2 PL-02097 Warsaw Poland Nagoya Univ Grad Sch Informat Chikusa Ku Furocho Nagoya Aichi 4648601 Japan JAIST Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan Iwate Univ Fac Sci & Engn Ueda 4-3-5 Morioka Iwate 0208551 Japan

Suppose that we are given two independent sets I-0 and I-r of a graph such that vertical bar I-0 vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I-0 into I-r so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I-0 and I-r with the minimum number of token movements. We finally show that one of the results for token jumping can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration Fixed parameter tractability graph algorithm Independent set

来源：评论

学校读者我要写书评

暂无评论

EvoArch: An evolutionary algorithm for architectural layout design

引用

COMPUTER-AIDED DESIGN 2009年第9期41卷 649-667页

作者： Wong, Samuel S. Y. Chan, Keith C. C. Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China

The architectural layout design problem, which is concerned with the finding of the best adjacencies between functional spaces among many possible ones under given constraints, can be formulated as a combinatorial optimization problem and can be solved with an Evolutionary algorithm (EA). We present functional spaces and their adjacencies in form of graphs and propose an EA called EvoArch that works with a graph-encoding scheme. EvoArch encodes topological configuration in the adjacency matrices of the graphs that they represent and its reproduction operators operate on these adjacency matrices. In order to explore the large search space of graph topologies, these reproduction operators are designed to be unbiased so that all nodes in a graph have equal chances of being selected to be swapped or mutated. To evaluate the fitness of a graph, EvoArch makes use of a fitness function that takes into consideration preferences for adjacencies between different functional spaces, budget and other design constraints. By means of different experiments, we show that EvoArch can be a very useful tool for architectural layout design tasks. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Architectural space topology Evolutionary algorithm Crossover Genetic algorithm graph algorithm Mutation

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of clique-transversal and clique-independent sets

引用

DISCRETE APPLIED MATHEMATICS 2000年第3期100卷 183-202页

作者： Guruswami, V Rangan, CP Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

A minimum clique-transversal set MCT(G) of a graph G = (V,E) is a set S subset of or equal to V of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocompatability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158-164). We present a polynomial algorithm for the above problems on Helly circular-are graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： graph algorithm NP-hardness clique-transversal set clique-independent set line graph total graph poset

来源：评论

学校读者我要写书评

暂无评论

Defending Against Malicious Influence Control in Online Leader-Follower Social Networks

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2024年 19卷 4809-4819页

作者： Zhu, Liwang Zhou, Xiaotian Tian, Jiahe Li, Wei Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Acad Engn & Technol Shanghai 200433 Peoples R China Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Res Inst Intelligent Complex Syst Shanghai 200433 Peoples R China

The formation of opinions is fundamentally a network-based process, where the opinions of individuals in a social network exchange, evolve, and eventually converge towards a specific distribution. However, this dynamic process may be susceptible to manipulation by adversarial entities, who aim to maliciously influence the opinion formulation. The adversary may engage in extensive influence campaigns, disseminating misinformation among populations, thereby potentially destabilizing societies. It is thus of significance to develop strategies to defend against such attacks, which are essential for fostering a healthy environment for information sharing, social deliberation, and opinion formation. In this paper, we investigate a scenario wherein an external adversary aims to maliciously alter the opinions of a general social graph. This is achieved by targeting several selected nodes, referred to as followers. Concurrently, we explore a counter-strategy, aiming to negate the influence of the adversary with malicious intents. This involves identifying a subset of nodes to act as followers of a defending leader, thereby minimizing the adversary's impact. Since this problem can be framed as a non-increasing supermodular minimization problem, we develop a $(1-1/e)$ approximation greedy algorithm consequently. Moreover, to overcome the computation challenge for large-scale networks, we establish an efficient approximation to the key quantity of the greedy algorithm. This refinement significantly enhances computational efficiency and scalability, making the algorithm applicable to networks with millions of nodes. Extensive simulation results on various real-world networks demonstrate the superior performance of our improved algorithm over existing algorithms and other baseline schemes based on centrality measures. In particular, our improved algorithm scales to networks of considerable size, with negligible sacrifice on the quality of solutions.

关键词： Opinion dynamics leader-follower social networks graph algorithm malicious influence control discrete optimization defense strategies

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for distance total domination in block graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期31卷 372-381页

作者： Zhao, Yancai Shan, Erfang Wuxi City Coll Vocat Technol Dept Basic Sci Wuxi 214153 Jiangsu Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China

The -distance total domination problem is to find a minimum vertex set of a graph such that every vertex of the graph is within distance from some vertex of other than itself, where is a fixed positive integer. In the present paper, by using a labeling method, we design an efficient algorithm for solving the -distance total domination problem on block graphs, a superclass of trees.

关键词： graph algorithm Total domination k-Distance total domination Block graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：