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

SIMPLE LINEAR-TIME algorithmS TO TEST CHORDALITY OF graphS, TEST ACYCLICITY OF HYPERgraphS, AND SELECTIVELY REDUCE ACYCLIC HYPERgraphS

引用

SIAM JOURNAL ON COMPUTING 1984年第3期13卷 566-579页

作者： TARJAN, RE YANNAKAKIS, M Bell Lab Murray Hill NJ USA Bell Lab Murray Hill NJ USA

Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. Rose, Tarjan and Lueker [SIAM J. Comput., 5 (1976), pp. 266–283] have given a linear-time algorithm to test whether a graph is chordal, which Yannakakis has modified to test whether a hypergraph is acyclic. Here we develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which we call maximum cardinality search A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acyclic relational data bases.

关键词： graph algorithm acyclic data base scheme sparse Gaussian elimination graph search hypergraph

来源：评论

学校读者我要写书评

暂无评论

Disk embeddings of planar graphs

引用

algorithmICA 2004年第4期38卷 539-576页

作者： Chen, ZZ He, X Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

Given a planar graph G = (V, E) and a rooted forest F = (V-F, A(F),) with leaf set V, we wish to decide whether G has a plane embedding 9 satisfying the following condition: There are \V-F\ - \V\ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of 17 such that for every nonleaf vertex f of F, the interior of the curve T-f corresponding to f contains all the leaf descendants of f in T but contains no other leaves of F. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex f in F induces a connected subgraph of G.

关键词： graph algorithm planar graph planar embedding

来源：评论

学校读者我要写书评

暂无评论

Balanced vertex-orderings of graphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第1期148卷 27-48页

作者： Biedl, T Chan, T Ganjali, Y Hajiaghayi, MT Wood, DR Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Stanford Univ Dept Elect Engn Stanford CA 94305 USA MIT Comp Sci Lab Cambridge MA 02139 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

In this paper we consider the problem of determining a balanced ordering of the vertices of a graph;, that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This problem, which has applications in graph drawing for example, is shown to be hard, and remains NP-hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13 / 8- approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size. (c) 2004, Elsevier B.V. All rights reserved.

关键词： graph algorithm graph drawing vertex-ordering balanced

来源：评论

学校读者我要写书评

暂无评论

On the tractability of some natural packing, covering and partitioning problems

引用

DISCRETE APPLIED MATHEMATICS 2015年 180卷 25-35页

作者： Bernath, Attila Kiraly, Zoltan Hungarian Acad Sci Inst Comp Sci & Control MTA SZTAKI Budapest Hungary Eotvos Lorand Univ Dept Comp Sci Budapest Hungary Eotvos Lorand Univ Egervary Res Grp MTA ELTE Budapest Hungary

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph G = (V, E) and two "object types" A and B chosen from the alternatives above, we consider the following questions. Packing problem: can we find an object of type A and one of type Bin the edge set E of G, so that they are edge-disjoint? Partitioning problem: can we partition E into an object of type A and one of type B? Covering problem: can we cover E with an object of type A, and an object of type B? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an s-t path P and an s'-t' path P' that are edge-disjoint. However, many others were not, for example can we find an s-t path P subset of E and a spanning tree T subset of E that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense). (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithm Packing Covering Partitioning Path Circuit Tree Forest Cut

来源：评论

学校读者我要写书评

暂无评论

algorithms for finding disjoint path covers in unit interval graphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 205卷 132-149页

作者： Park, Jung-Heum Choi, Joonsoo Lim, Hyeong-Seok Catholic Univ Korea Sch Comp Sci & Informat Engn Seoul South Korea Kookmin Univ Sch Comp Sci Seoul South Korea Chonnam Natl Univ Sch Elect & Comp Engn Gwangju South Korea

A many-to-many k-disjoint path cover (k-DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T, each of size k, is a collection of k vertex-disjoint paths between S and T, which altogether cover every vertex of G. This is classified as paired, if each vertex of S must be joined to a specific vertex of T, or unpaired, if there is no such constraint. In this paper, we develop a linear-time algorithm for the UNPAIRED DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the ONE-TO-ONE DPC and the ONE-TO-MANY DPC problems are reduced in linear time. Additionally, we show that the PAIRED k-DPC problem on a unit interval graph is polynomially solvable for any fixed k. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Disjoint path Path cover Path partition Proper interval graph graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Theoretical Analysis of Git Bisect

引用

algorithmICA 2024年第5期86卷 1365-1399页

作者： Courtiel, Julien Dorbec, Paul Lecoq, Romain Normandie Univ UNICAEN CNRS ENSICAENGREYC F-14000 Caen France

In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a directed acyclic graph (DAG) where vertices represent versions of the software, and arcs are the changes between different versions. We assume that somewhere in the DAG, a bug was introduced, which persists in all of its subsequent versions. It is possible to query a vertex to check whether the corresponding version carries the bug. Given a DAG and a bugged vertex, the Regression Search Problem consists in finding the first vertex containing the bug in a minimum number of queries in the worst-case scenario. This problem is known to be NP-complete. We study the algorithm used in git to address this problem, known as git bisect. We prove that in a general setting, git bisect can use an exponentially larger number of queries than an optimal algorithm. We also consider the restriction where all vertices have indegree at most 2 (i.e. where merges are made between at most two branches at a time in the VCS), and prove that in this case, git bisect is a 1/log(2)(3/2)-approximation algorithm, and that this bound is tight. We also provide a better approximation algorithm for this case. Finally, we give an alternative proof of the NP-completeness of the Regression Search Problem, via a variation with bounded indegree.

关键词： graph algorithm Approximation algorithm Regression search Worst-case complexity Version control system

来源：评论

学校读者我要写书评

暂无评论

The perfect matching cut problem revisited

引用

THEORETICAL COMPUTER SCIENCE 2022年 931卷 117-130页

作者： Le, Van Bang Telle, Jan Arne Univ Rostock Inst Informat Rostock Germany Univ Bergen Dept Informat N-5020 Bergen Norway

In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We revisit the problem and show that PMC remains NP-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which PMC is polynomial-time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no O*(2o(n))-time algorithm for PMC even when restricted to n-vertex bipartite graphs, and also show that PMC can be solved in O*(1.2721n) time by means of an exact branching algorithm.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Matching cut Perfect matching cut Computational complexity Exact branching algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Balanced Clique Computation in Signed Networks: Concepts and algorithms

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第11期35卷 11079-11092页

作者： Chen, Zi Yuan, Long Lin, Xuemin Qin, Lu Zhang, Wenjie East China Normal Univ Software Engn Inst Shanghai 200050 Peoples R China Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Peoples R China Univ New South Wales Sch Comp Sci & Engn Sydney NSW 2052 Australia Univ Technol Ctr QCIS Sydney NSW 2007 Australia

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study the maximal balanced clique enumeration problem (MBCE) which computes all the maximal balanced cliques in a given signed network. Moreover, in some applications, users prefer a unique and representative balanced clique with maximum size rather than all balanced cliques. Thus, we also study the maximum balanced clique search problem (MBCS) which computes the balanced clique with maximum size. We show that MBCE problem and MBCS problem are both NP-Hard. For the MBCE problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the MBCS problem, we first propose a baseline solution. To overcome the huge search space problem of the baseline solution, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments

关键词： Balanced clique structural balance theory signed network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Maintaining balanced trees for structured distributed streaming systems

引用

DISCRETE APPLIED MATHEMATICS 2017年 232卷 176-188页

作者： Giroire, F. Modrzejewski, R. Nisse, N. Perennes, S. Univ Nice Sophia Antipolis CNRS I3S UMR 7271 F-06900 Sophia Antipolis France Google Dublin Ireland INRIA Rocquencourt France

In this paper, we propose and analyze a simple local algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced binary tree in O(n(2)) rounds. We then describe a more restrictive model, adding a small extra information to each node, under which we adapt our algorithm to converge in circle minus(n log n) rounds. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed live streaming system graph algorithm Balanced trees Peer-to-peer

来源：评论

学校读者我要写书评

暂无评论

Hardness and Structural Results for Half-Squares of Restricted Tree Convex Bipartite graphs

引用

algorithmICA 2019年第11-12期81卷 4258-4274页

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

Let B=(X,Y,E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X;two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514-523. 10.1145/276698.276865, 1998;J ACM 49(2):127-138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O(n120)-time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396-405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares.

关键词： Half-square NP-hardness graph algorithm Computational complexity graph classes 68R10 05C85 68Q25

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：