Algorithm 447
Algorithm 447: effcient algorithms for graph manipulation. Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer,
This software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 161 articles )
Showing results 1 to 20 of 161.
Sorted by year (- Bang-Jensen, Jørgen; Schweser, Thomas; Stiebitz, Michael: Digraphs and variable degeneracy (2022)
- Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Monaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S.: Almost envy-free allocations with connected bundles (2022)
- Brettell, Nick; Johnson, Matthew; Paesani, Giacomo; Paulusma, Daniël: Computing subset transversals in (H)-free graphs (2022)
- Crespelle, Christophe; Golovach, Petr A.: Cyclability in graph classes (2022)
- Frati, Fabrizio: Planar rectilinear drawings of outerplanar graphs in linear time (2022)
- Horváth, Markó; Kis, Tamás; Kovács, András; Fekula, Márk: Assembly planning by disjunctive programming and geometrical reasoning (2022)
- Marzorati, Denise; Fernández, Joaquin; Kofman, Ernesto: Efficient connection processing in equation-based object-oriented models (2022)
- Akitaya, Hugo A.; Biniaz, Ahmad; Bose, Prosenjit: On the spanning and routing ratios of the directed (\varTheta_6)-graph (2021)
- Beisegel, Jesse; Denkert, Carolin; Köhler, Ekkehard; Krnc, Matjaž; Pivač, Nevena; Scheffler, Robert; Strehler, Martin: The recognition problem of graph search trees (2021)
- Carlsson, Gunnar; Mémoli, Facundo; Segarra, Santiago: Robust hierarchical clustering for directed networks: an axiomatic approach (2021)
- Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter: Kernelization of graph Hamiltonicity: proper (H)-graphs (2021)
- Da Lozzo, Giordano; Eppstein, David; Goodrich, Michael T.; Gupta, Siddharth: C-planarity testing of embedded clustered graphs with bounded dual carving-width (2021)
- Devillers, Raymond: Articulations and products of transition systems and their applications to Petri net synthesis (2021)
- Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Tais, Marco: Schematic representation of large biconnected graphs (2021)
- Hojny, Christopher; Joormann, Imke; Lüthen, Hendrik; Schmidt, Martin: Mixed-integer programming techniques for the connected max-(k)-cut problem (2021)
- Jansson, Jesper; Mampentzidis, Konstantinos; Rajaby, Ramesh; Sung, Wing-Kin: Computing the rooted triplet distance between phylogenetic networks (2021)
- Pattison, Tim; Ceglar, Aaron: Towards interactive transition from AOC poset to concept lattice (2021)
- Pérez, Claudia; Rivera, Daniel: Polynomial-time classification of skew-symmetrizable matrices with a positive definite quasi-Cartan companion (2021)
- Zamberletti, Patrizia; Papaïx, Julien; Gabriel, Edith; Opitz, Thomas: Markov random field models for vector-based representations of landscapes (2021)
- Zhang, Xindi; Li, Bohan; Cai, Shaowei; Wang, Yiyuan: Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set (2021)