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

CONTRACTIONS, REMOVALS, AND certifying 3-CONNECTIVITY IN LINEAR TIME

SIAM JOURNAL ON COMPUTING 2013年第2期42卷 494-535页

作者： Schmidt, Jens M. Max Planck Inst Informat D-66123 Saarbrucken Germany

One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K-4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grunbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(vertical bar V vertical bar(2)) to O(vertical bar E vertical bar). This result has a number of consequences;an important one is a new linear-time test of 3-connectivity that is certifying;finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(vertical bar E vertical bar). We show how to extend the results to an optimal certifying test of 3-edge-connectivity.

关键词： construction sequence certifying algorithm 3-connected graph inductive characterization nested subdivisions

来源：评论

学校读者我要写书评

暂无评论

certifying 3-Edge-Connectivity

引用

algorithmICA 2017年第2期77卷 309-335页

作者： Mehlhorn, Kurt Neumann, Adrian Schmidt, Jens M. Max Planck Inst Informat Saarbrucken Germany

We present a certifying algorithm that tests graphs for 3-edge-connectivity;the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.

关键词： certifying algorithm Edge connectivity Construction sequence

来源：评论

学校读者我要写书评

暂无评论

Construction Sequences and certifying 3-connectivity

引用

algorithmICA 2012年第1-2期62卷 192-208页

作者： Schmidt, Jens M. Free Univ Berlin Dept Comp Sci Berlin Germany

Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K (4) can be computed in O(|V|(2)) time by extending Barnette's and Grunbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.

关键词： algorithms and data structures Construction sequence 3-connected certifying algorithm Tutte contraction Removable edges

来源：评论

学校读者我要写书评

暂无评论

certifying Induced Subgraphs in Large Graphs 17th

Certifying Induced Subgraphs in Large Graphs

引用

17th International Conference and Workshops on algorithms and Computation

作者： Meyer, Ulrich Tran, Hung Tsakalidis, Konstantinos Goethe Univ Frankfurt Frankfurt Germany Univ Liverpool Liverpool Merseyside England

ISBN: (纸本)9783031270505;9783031270512

We introduce I/O-effiient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with n vertices and m edges, our algorithms take O(SORT(n + m)) I/Os in the worst case for split, threshold and trivially perfect graphs. In the same complexity bipartite and bipartite chain graphs can be certified with high probability. We provide implementations for split and threshold graphs and provide a preliminary experimental evaluation.

关键词： certifying algorithm Graph algorithm External memory

来源：评论

学校读者我要写书评

暂无评论

Construction Sequences and certifying 3-Connectedness

Construction Sequences and Certifying 3-Connectedness

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Schmidt, Jens M. Freie Univ Dept Comp Sci Berlin Germany

ISBN: (纸本)9783939897163

Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from C to the K-4 can be computed in O(|V|(2)) time by extending Barnette and Grunbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.

关键词： algorithms and data structures construction sequence 3-connected certifying algorithm Tutte contraction removable edges

来源：评论

学校读者我要写书评

暂无评论

Linear-Time algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs

引用

algorithmICA 2022年第4期84卷 1064-1080页

作者： Klemz, Boris Rote, Guenter Univ Wurzburg Inst Informat D-97074 Wurzburg Germany Free Univ Berlin Inst Informat Takustr 9 D-14195 Berlin Germany

A bipartite graph G = (U, V, E) is convex if the vertices in V can be linearly ordered such that for each vertex u is an element of U, the neighbors of u are consecutive in the ordering of V. An induced matching H of G is amatching for which no edge of E connects endpoints of two different edges of H. We show that in a convex bipartite graph with n vertices and m weighted edges, an induced matching of maximum total weight can be computed in O(n + m) time. An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex u is an element of U the first and last neighbor in the ordering of V. Given such a compact representation, we compute an induced matching of maximum cardinality in O(n) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O(n) time. If no compact representation is given, the cover can be computed in O(n+ m) time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of O(n(2)) (Brandstadt et al. in Theor. Comput. Sci. 381(1-3):260-265, 2007. https://***/10.1016/***.2007.04.006). The weighted case has not been considered before.

关键词： Graph algorithm Induced matching Chain cover Convex bipartite graph certifying algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Better 3-coloring algorithms: Excluding a triangle and a seven vertex path

引用

THEORETICAL COMPUTER SCIENCE 2021年 850卷 98-115页

作者： Bonomo-Braberman, Flavia Chudnovsky, Maria Goedgebeur, Jan Maceli, Peter Schaudt, Oliver Stein, Maya Zhong, Mingxian Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires DF Argentina Univ Buenos Aires CONICET Inst Invest Ciencias Comp ICC Buenos Aires DF Argentina Princeton Univ Princeton NJ 08544 USA Univ Ghent Ghent Belgium Univ Mons Mons Belgium Ithaca Coll Ithaca NY 14850 USA Univ Cologne Cologne Germany Univ Chile Santiago Chile CUNY Lehman Coll Bronx NY 10468 USA CUNY Grad Ctr Bronx NY 10468 USA

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1, 2, 3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(vertical bar V (G)vertical bar(5)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)), and if G is bipartite, it improves to O(vertical bar V (G)vertical bar(2)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {P-t, C-3}-free graphs if and only if t <= 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P-7, C-3}-free graphs. We furthermore determine other cases of t, l, and k such that the family of minimal obstructions to list k-coloring in {P-t, C-l}-free graphs is finite. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithm Graph coloring certifying algorithm Forbidden induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

Computing Vertex-Disjoint Paths in Large Graphs Using MAOs

引用

algorithmICA 2020年第1期82卷 146-162页

作者： Preisser, Johanna E. Schmidt, Jens M. TU Ilmenau Inst Math Ilmenau Germany

We consider the problem of computing k is an element of N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, O(min{k,n}m) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every 1 <= k <=delta (where delta is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last delta-k+2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time O(n+m), which improves the previously best time O(min{k,n}m). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.

关键词： Computing disjoint paths Large graphs Vertex-connectivity Linear-time Maximal adjacency ordering Maximum cardinality search Big data certifying algorithm

来源：评论

学校读者我要写书评

暂无评论

Unit interval editing is fixed-parameter tractable

引用

INFORMATION AND COMPUTATION 2017年第Part1期253卷 109-126页

作者： Cao, Yixin Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China

Given a graph G and integers k(1), k(2), and k(3), the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k(1) vertex deletions, k(2) edge deletions, and k(3) edge additions. We give an algorithm solving this problem in time 2(o(klogk)). (n+m), where k := k(1) + k(2) + k(3), and n,m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed -parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O(4(k) (n +m)). Another result is an 0 (6(k) . (n +m))-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O(6(k) .n(6)). (C) 2017 Elsevier Inc. All rights reserved.

关键词： Graph modification problem Forbidden induced subgraph Proper Helly circular-arc graph (Proper,unit) interval model (Proper,Helly) arc model certifying algorithm {Claw,S-3, (S)over-bar(3), C-4}-free graph

来源：评论

学校读者我要写书评

暂无评论

A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix

引用

INFORMATION PROCESSING LETTERS 2012年第20期112卷 799-803页

作者： Malekesmaeili, Mehrnoush Chauve, Cedric Stephen, Tamon Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada

A binary matrix has the Consecutive Ones Property (C1P) if it is possible to order the columns so that all Is are consecutive in every row. In [McConnell, SODA 2004, pp. 768-777] the notion of incompatibility graph of a binary matrix was introduced and it was shown that odd cycles of this graph provide a certificate that a matrix does not have the Consecutive Ones Property. A bound of k + 2 was claimed for the smallest odd cycle of a non-C1P matrix with k columns. In this Note we show that this result can be obtained simply and directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Consecutive Ones Property Tucker patterns certifying algorithm Incompatibility graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：