Dividing a Graph into Triconnected Components
From MaRDI portal
Publication:4767335
DOI10.1137/0202012zbMath0281.05111WikidataQ29394586 ScholiaQ29394586MaRDI QIDQ4767335
Robert Endre Tarjan, John E. Hopcrofts
Publication date: 1973
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6037
68W40: Analysis of algorithms
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
The exact overall time distribution of a project with uncertain task durations, Decomposition plans for geometric constraint systems. I: Performance measures for CAD, Guthrie's problem: new equivalences and rapid reductions, Recognising \(k\)-connected hypergraphs in cubic time, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, The decomposition of graphs into \(k\)-connected components, The anti-join composition and polyhedra, Locating facilities which interact: Some solvable cases, Counting labelled three-connected and homeomorphically irreducible two- connected graphs, Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs, Testing planar pictures for isomorphism in linear time, A linear-time algorithm for finding an ambitus, A new graph triconnectivity algorithm and its parallelization, Deciding whether graph \(G\) has page number one is in NC, An extension of the multi-path algorithm for finding Hamilton cycles, Detecting cycles through three fixed vertices in a graph, A linear time algorithm for computing 3-edge-connected components in a multigraph, Parallel search algorithms for graphs and trees, A minimum 3-connectivity augmentation of a graph, A linear algorithm for the all-bidirectional-edges problem on planar graphs, Graph isomorphism, general remarks, Faster approximation algorithms for weighted triconnectivity augmentation problems, On testing consecutive-ones property in parallel, Advances in the theory and practice of graph drawing, Balanced cycles and holes in bipartite graphs, Uncovering generalized-network structure in matrices, Representing polyhedra: Faces are better than vertices, Independent trees in graphs, Data structures for two-edge connectivity in planar graphs, On the equivalence of constrained and unconstrained flows, Planarity testing in parallel, The input/output complexity of transitive closure, Edge-packing planar graphs by cyclic graphs, Projective plan and Möbius band obstructions, Relational depth-first-search with applications, Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation, 4-edge-coloring graphs of maximum degree 3 in linear time, A smallest augmentation to 3-connect a graph, A note on finding the bridges of a graph, Sewing ribbons on graphs in space, Incremental convex planarity testing, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, The arborescence-realization problem, Upward planarity testing, A decomposition algorithm for network reliability evaluation, Drawing planar graphs using the canonical ordering, Efficient algorithmic learning of the structure of permutation groups by examples, Orthogonal drawings of graphs for the automation of VLSI circuit design, Decomposition of 3-connected graphs, Blocks in \(k\)-connected graphs, Linear time algorithms for graph search and connectivity determination on complement graphs., An improved algorithm for decomposing arc flows into multipath flows, Finding all minimum-size separating vertex sets in a graph
