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

Map graphs having witnesses of large girth

THEORETICAL COMPUTER SCIENCE 2019年 772卷 143-148页

作者： Le, Hoang-Oanh Le, Van Bang Univ Rostock Inst Informat Rostock Germany

A half-square of a bipartite graph B = (X, Y, E-B) has one color class of B as vertex set, say X;two vertices are adjacent whenever they have a common neighbor in Y. If G = (V, E-G) is the half-square of a planar bipartite graph B = (V, W, E-B), then G is called a map graph, and B is a witness of G. Map graphs generalize planar graphs, and have been introduced and investigated by Chen, Grigni and Papadimitriou [STOC 1998, J. ACM 2002]. They proved that recognizing map graphs is in NP by proving the existence of a witness. Soon later, Thorup [FOCS 1998] claimed that recognizing map graphs is in P, by providing an Omega(n(120)) time algorithm for n-vertex input graphs. In this note, we give good characterizations and efficient recognition for half-squares of bipartite graphs with girth at least a given integer g >= 8. It turns out that map graphs having witnesses of girth at least g are precisely the graphs whose vertex-clique incidence bipartite graph is planar and of girth at least g. Our structural characterization implies an O(n(2)m)-time algorithm for recognizing if a given n-vertex m-edge graph G is such a map graph. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Map graph Half-square graph class graph algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of open neighborhood location-domination in graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part1期216卷 290-306页

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

A set D subset of V of a graph G = (V, E) is called an open neighborhood locating-dominating set (OLD-set) if (i)N-G(v) boolean AND D not equal empty set for all v is an element of V, and (ii)N-G(u) boolean AND D not equal N-G(v) boolean AND D for every pair of distinct vertices u, v is an element of V. Given a graph G = (V, E), the MIN OLD-SET problem is to find an OLD-set of minimum cardinality. Given a graph G = (V, E) and a positive integer k, the DECIDE OLD-SET problem is to decide whether G has an OLD-set of cardinality at most k. The DECIDE OLD-SET problem is known to NP-complete for general graphs. In this paper we extend the NP-completeness result of the DECIDE OLD-SET problem by showing that it remains NP-complete for bipartite graphs, planar graphs, split graphs and doubly chordal graphs. We prove that the DECIDE OLD-SET problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for the MIN OLD SET problem in trees. We also propose a (2 + 3 ln Delta)-approximation algorithm for the MIN OLD-SET problem and show that the MIN OLD-SET problem cannot be approximated within 1/2(1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless NP subset of DTIME(vertical bar V vertical bar(0(log log vertical bar V vertical bar))) Finally, we prove that the MIN OLD-SET problem is APX-complete for bipartite graphs of maximum degree 3. (C) 2015 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Alliances in graphs of bounded clique-width

引用

DISCRETE APPLIED MATHEMATICS 2017年 223卷 91-97页

作者： Kiyomi, Masashi Otachi, Yota Yokohama City Univ Int Coll Arts & Sci Kanazawa Ku 22-2 Seto Yokohama Kanagawa 2360027 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs. In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

关键词： graph algorithm Alliance Clique-width Vertex cover

来源：评论

学校读者我要写书评

暂无评论

Vertex cover-based binary tree algorithm to detect all maximum common induced subgraphs in large communication networks

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2016年第1期48卷 229-252页

作者： Nirmala, Parisutham Lekshmi, Ramasubramony Sulochana Nadarajan, Rethnasamy PSG Coll Technol Dept Appl Math & Computat Sci Coimbatore 641004 Tamil Nadu India

Maximum common induced subgraph (MCIS) of a communication network graph database determine the common substructures which are always active and retain the links between any pair of nodes exactly as in all graphs of the database. Many benchmark graph algorithms to predict MCIS of a graph database deal only with two graphs at a time and seek isomorphism, for which a high computational cost is to be paid. This gradually reduces the performance of the existing algorithms when the database has huge graph data. The proposed binary caterpillar MCIS algorithm to predict all MCIS of the database works for communication network graph database each of whose vertices has a unique label (IP address). In this, a new data structure which is a caterpillar-based binary tree is defined to reduce the search space of the problem using the concept of vertex cover and it takes into account all graphs of the database simultaneously to predict all MCIS of the database. This has substantially reduced unwanted comparisons among the datasets, when compared to the existing algorithms, as well as the difficulty of seeking isomorphism is avoided due to unique vertex labels. The experimental results further ensure the efficiency of the proposed algorithm with respect to existing works.

关键词： Communication networks Similarity pattern graph mining Substructure mining Subgraph isomorphism Information extraction graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra algorithms

引用

JOURNAL OF COMPUTING IN CIVIL ENGINEERING 2013年第3期27卷 263-273页

作者： Pradhan, Anu Mahinthakumar, G. (Kumar) Drexel Univ Dept Civil Architectural & Environm Engn Philadelphia PA 19104 USA N Carolina State Univ Dept Civil Construct & Environm Engn Raleigh NC 27695 USA

Parallel computing has become a powerful approach for solving real-time decisions about large-scale, computing-intensive transportation problems. A frequently encountered transportation problem is the "shortest path problem;" that is, finding the shortest path between any two nodes in a transportation network. For the large transportation networks encountered in major metropolitan areas, this problem can be computationally demanding, especially if shortest paths between all the nodes in the network need to be dynamically updated (e. g., evolving traffic conditions). In such a situation, one may wish to harness parallel computing to solve this problem. However, the parallel implementations of commonly used shortest-path algorithms are computationally demanding because of the inherent sequential nature of the search process used by the algorithms. This paper describes parallel implementations and includes performance analyses of two prominent graph algorithms (i.e., Floyd-Warshall and Dijkstra) used for finding the all-pairs shortest path for a large-scale transportation network. The results indicate that a multilevel parallel implementation that combines message passing interface (MPI) with shared memory threads [e. g., Open Multiprocessing (OpenMP) or POSIX Threads (pthreads)] is effective for solving these problems on a moderate number of symmetric multiprocessor (SMP) nodes. This paper also includes the derivation of the computational time for the different parallel implementations of these two graph algorithms. DOI: 10.1061/(ASCE)CP.1943-5487.0000220. (C) 2013 American Society of Civil Engineers.

关键词： Parallel computing graph algorithm Transportation Computing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：