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

Circular right-angle crossing drawings in linear time

THEORETICAL COMPUTER SCIENCE 2016年 639卷 26-41页

作者： Dehkordi, Hooman Reisi Eades, Peter Hong, Seok-Hee Quan Nguyen Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

A common representational style for drawing graphs is the so-called circular drawings, where vertices are represented as points on a circle, and edges are represented as straight line segments. In such drawings, edges may cross;these edge crossings have a negative effect on human readability. Recent empirical research shows that increasing the angles of edge crossings reduces the negative effect of crossings on human readability. This result has motivated a number of recent investigations of right angle crossing graph drawings, where each crossing angle is The main result of this paper is a characterization of graphs that admit a circular right angle crossing drawing. We present a linear-time algorithm for testing and constructing such a drawing of a graph, if it exists. Further, we give an upper bound on the number of edges in a circular right angle crossing drawing, and we note that the optimization problem of constructing circular drawings with large angle crossings can be formulated as a quadratic programming problem. (C) 2016 Elsevier B.V. All rights reserved.

关键词： graph algorithm graph drawing Right angle crossing RAC Circular Straight-line Embedding Layout

来源：评论

学校读者我要写书评

暂无评论

Approximation to the Minimum Cost Edge Installation Problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2010年第4期E93A卷 778-786页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

We consider the minimum cost edge installation problem (MCEI) in a graph G = (V, E) with edge weight w(e) >= 0. e is an element of E We are given a vertex s is an element of V designated as a sink, an edge capacity lambda > 0. and a source set S subset of V with demand q(v) is an element of |0,lambda|, v is an element of S For each edge e is an element of E. we are allowed to install an integer number h(e) of copies of e MCEI asks to send demand q(v) from each source v is an element of S along a single path P-v to the sink without splitting the demand of any source v is an element of S For each edge e is an element of E. a set of such paths can pass through a single copy of e in C as long as the total demand along the paths does not exceed the edge capacity lambda The objective is to find a set P = {P-v | v is an element of S} of paths of G that minimizes the installing cost Sigma(eCE) h(e)w(e) In this paper. we propose a (15/8 + rho(ST))-approximation algorithm to MCEI. where rho(SI) is any approximation ratio achievable tor the Steiner tree problem

关键词： approximation algorithm graph algorithm routing problem network optimization

来源：评论

学校读者我要写书评

暂无评论

NETWORK PERTURBATIONS AND ASYMPTOTIC PERIODICITY OF RECURRENT FLOWS IN INFINITE NETWORKS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2009年第3期23卷 1561-1574页

作者： Kunszenti-Kovacs, David Univ Tubingen Dept Math D-72076 Tubingen Germany

We extend the main result by Dorn, Keicher, and Sikolya from [Math. Z., 263 (2009), pp. 69-87] on the asymptotic periodicity of flows in infinite networks. To this purpose we develop an algorithmic perturbation technique for infinite networks allowing us to change edge lengths without changing the asymptotic behavior. The asymptotic limit is identified with a (periodic) flow in a factor network consisting of a single loop.

关键词： infinite directed graph flow semigroup asymptotic behavior factor network set-valued distance graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Post-processing hierarchical community structures: Quality improvements and multi-scale view

引用

THEORETICAL COMPUTER SCIENCE 2011年第8-10期412卷 892-900页

作者： Pons, Pascal Latapy, Matthieu CNRS LIP6 F-75005 Paris France Univ Paris 06 F-75005 Paris France

Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of communities and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity based quality function which we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect different scales at which meaningful community structures appear, while classical approaches find only one partition. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Hierarchical clustering Community detection Complex network graph algorithm Multi-scale

来源：评论

学校读者我要写书评

暂无评论

Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1363-1374页

作者： Nakahata, Yu Kawahara, Jun Horiyama, Takashi Kasahara, Shoji Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300192 Japan Saitama Univ Grad Sch Sci & Engn Saitama 3388570 Japan

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

关键词： graph algorithm graph partitioning decision diagram frontier-based search enumeration problem

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for maximum edge colouring problem

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 42-52页

作者： Chandran, L. Sunil Lahiri, Abhiruk Singh, Nitin Indian Inst Sci Dept Comp Sci & Automat Bangalore India IBM India Res Lab Bangalore India

The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdos and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a colouring of the edges of G, maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals ar(G, K1,q+1) - 1. In this paper, we study the maximum edge 2-colouring problem from the approx-imation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. algorithmically, this problem is known to be NP-hard for q - 2. For the case of q = 2, it is also known that no polynomial-time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5/3-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G \ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8/5. We also show that this algorithm cannot achieve a factor better than 58/37 o

关键词： Approximation algorithm graph algorithm graph colouring Anti-Ramsey number

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs

引用

algorithmICA 2020年第10期82卷 3066-3090页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d min, d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min = d max such that G has an edge between two vertices u, v. V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d min, d max]. The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph Polynomial-time algorithm graph algorithm graph theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：