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

A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

THEORETICAL COMPUTER SCIENCE 2019年 770卷 69-78页

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

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP complete even when restricted to bipartite graphs. It has been proved that MATCHING CUT is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d >= 3, MATCHING CUT is NP-complete in the class of graphs of diameter d. This resolves an open problem posed by Borowiecki and Jesse-Jozefczyk (2008) [6]. We then show that, for any fixed integer d >= 4, MATCHING CUT is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that MATCHING CUT is polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving MATCHING CUT in graphs of diameter 2. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Matching cut NP-hardness graph algorithm Computational complexity Dichotomy theorem Decomposable graph

来源：评论

学校读者我要写书评

暂无评论

First Fast Sink: A compiler algorithm for barrier placement optimisation

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 1998年第4-5期13卷 397-406页

作者： Stohr, EA O'Boyle, MFP Univ Manchester Dept Comp Sci Manchester M13 9PL Lancs England Univ Edinburgh Dept Comp Sci Edinburgh EH9 3JZ Midlothian Scotland

This paper describes a new compiler algorithm to reduce the number of barrier synchronisations in parallelised programs. A preliminary technique to rapidly determine critical data dependences is developed. This forms the basis of the First Fast Sink (FFS) algorithm which places, provably, the minimal number of barriers in polynomial time for codes with a regular structure. This algorithm is implemented in a prototype compiler and applied to three well known benchmarks. Preliminary results show that it outperforms an existing state-of-the-art commercial compiler. Copyright (C) 1998 Elsevier Science B.V.

关键词： barrier synchronisation optimising compilation graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum edge ranking spanning trees of split graphs

引用

DISCRETE APPLIED MATHEMATICS 2006年第16期154卷 2373-2386页

作者： Makino, Kazuhisa Uno, Yushi Ibaraki, Toshihide Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan Univ Tokyo Grad Sch Informat & Technol Dept Math Informat Tokyo 1138656 Japan Kwansei Gakuin Univ Sch Sci & Technol Dept Informat Sanda 6691337 Japan

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split. (c) 2006 Elsevier B.V. All rights reserved.

关键词： edge ranking minimum edge ranking spanning tree split graphs threshold graphs graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Crossing minimization in extended level drawings of graphs

引用

DISCRETE APPLIED MATHEMATICS 2010年第3期158卷 159-179页

作者： Bachmaier, Christian Buchner, Hedi Forster, Michael Hong, Seok-Hee Univ Passau Fac Inf & Math D-94030 Passau Germany Natl ICT Australia IMAGEN Program Eveleigh NSW 1430 Australia Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles. In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings. We first show that the extended one-sided crossing minimization problem is N P-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings. (C) 2009 Elsevier B.V. All rights reserved.

关键词： (Radial) level graph Crossing minimization Intra-level edges Hierarchy Level/layered drawing Visualization of social networks graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第4期70卷 406-415页

作者： Guellati, Nabil Kheddouci, Hamamache Univ Abderrahmane Mira Dept Comp Sci Bejaia Algeria Univ Lyon 1 LIESP Lab F-69365 Lyon France

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Distributed algorithm Self-stabilization graph algorithm Independence Domination Coloring Matching

来源：评论

学校读者我要写书评

暂无评论

The minimum all-ones problem for trees

引用

SIAM JOURNAL ON COMPUTING 2004年第2期33卷 379-392页

作者： Chen, WYC Li, XL Wang, C Zhang, XY Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

The minimum all-ones problem was shown to be NP-complete for general graphs. Therefore, it becomes an interesting problem to identify special classes of graphs for which one can find polynomial time algorithms. In this paper we consider this problem for trees. First, for any solution to the all-ones problem for a tree, we give a characterization of the elements in the solution by introducing the concept of the quasi all-ones problem. Then we give the enumeration for the number of solutions in a tree. By using the minimum odd (even) sum problem as subprocess, we obtain a linear time algorithm for the minimum all-ones problem for trees. We also get a linear time algorithm for finding solutions to the all-ones problem in a unicyclic graph.

关键词： lamp lighting problem all-ones problem graph algorithm time complexity

来源：评论

学校读者我要写书评

暂无评论

Liar's domination in graphs: Complexity and algorithm

引用

DISCRETE APPLIED MATHEMATICS 2013年第7-8期161卷 1085-1092页

作者： Panda, B. S. Paul, S. Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

A set L subset of V (G) of a graph G = (V, E) is a liar's dominating set if (1) for all v is an element of V (G), vertical bar N-G[v]boolean AND L vertical bar >= 2 and (2) for every pair u, v is an element of V (G) of distinct vertices, vertical bar(N-G[u] boolean OR N-G[v]) boolean AND L vertical bar >= 3. A graph G = (V, E) admits a liar's dominating set if each of its connected component has at least three vertices. Given a graph G = (V, E) and an integer K, the liar's domination decision problem (LR-DOMDP) is to decide whether G has a liar's dominating set of cardinality at most K. Slater [P.J. Slater, Liar's Domination, Networks, 54(2) (2009) 70-74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar's domination in graphs, Discrete Math., 309(19) (2009) 5884-5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar's dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar's dominating set in a tree. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm NP-completeness Domination Liar's domination

来源：评论

学校读者我要写书评

暂无评论

LOCAL FLOW PARTITIONING FOR FASTER EDGE CONNECTIVITY

引用

SIAM JOURNAL ON COMPUTING 2020年第1期49卷 1-36页

作者： Henzinger, Monika Rao, Satish Wang, Di Univ Vienna A-1090 Vienna Austria Univ Calif Berkeley Comp Sci Div Berkeley CA 94720 USA Georgia Inst Technol Atlanta GA 30332 USA

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log(2) n log log(2) n) time algorithm. This improves on both the best previously known deterministic running time of O(m log(12) n) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 41) and the best previously known randomized running time of O(m log(3) n) (Karger [J. ACM, 47 (2000), pp. 46-761) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow-and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.

关键词： min cut graph algorithm deterministic algorithm flow edge connectivity local algorithm

来源：评论

学校读者我要写书评

暂无评论

The List Coloring Reconfiguration Problem for Bounded Pathwidth graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1168-1178页

作者： Hatanaka, Tatsuhiko Ito, Takehiro Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.

关键词： graph algorithm list coloring pathwidth PSPACE-complete reachability on solution space reconfiguration

来源：评论

学校读者我要写书评

暂无评论

Shortest paths avoiding forbidden subpaths

引用

NETWORKS 2013年第4期61卷 322-334页

作者： Ahmed, Mustaq Lubiw, Anna Google Inc Mountain View CA USA Univ Waterloo DRC Sch Comp Sci Waterloo ON N2L 3G1 Canada

We study a variant of the shortest path problem in graphs: given a weighted graph Gand vertices sand t, and given a set Xof forbidden paths in G, find a shortest s- tpath Psuch that no path in Xis a subpath of P. Path Pis allowed to repeat vertices and edges. We call each path in Xan exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception xXonly when a path containing xfails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The main idea is to use a shortest path algorithm incrementally after replicating vertices when an exception is discovered. (c) 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013

关键词： graph algorithm Dijkstra optical network road network exception avoiding path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：