Algorithm 447 swMATH ID: 12877 Software Authors: J. Hopcroft; R. Tarjan Description: 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, Homepage: http://dl.acm.org/citation.cfm?id=362272 Related Software: SNAP; Boost; MIPLIB; CPLEX; SCIP; NodeTrix; R; SANET; LAPACK; igraph; Mathematica; Julia; DIMACS; MIPLIB2003; PORTA; Algorithm 457; Gurobi; GDToolkit; SuMoTED; tqDist Cited in: 172 Publications all top 5 Cited by 397 Authors 4 Saurabh, Saket 4 Tarjan, Robert Endre 3 Bose, Prosenjit K. 3 Chimani, Markus 3 Fomin, Fedor V. 3 Granot, Frieda 3 Jansen, Bart M. P. 3 Lokshtanov, Daniel 3 Scheffler, Robert 3 Trotignon, Nicolas 3 Ullman, Jeffrey David 2 Akitaya, Hugo A. 2 Beisegel, Jesse 2 Berry, Anne 2 Biniaz, Ahmad 2 Brettell, Nick 2 Chaplick, Steven 2 Da Lozzo, Giordano 2 Denkert, Carolin 2 Ducoffe, Guillaume 2 Even, Shimon 2 Fang, Wenjie 2 Frati, Fabrizio 2 Gautier, Antoine 2 Golovach, Petr A. 2 Igarashi, Ayumi 2 Ihm, Insung 2 Ilsen, Max 2 Jovanović, Raka 2 Kim, Eunjung 2 Köhler, Ekkehard 2 Korach, Ephraim 2 Krnc, Matjaž 2 Kwon, Ojoung 2 Marx, Dániel 2 Misra, Pranabendu 2 Moataz, Fatima Zahra 2 Nisse, Nicolas 2 Ostfeld, Zvi 2 Panolan, Fahad 2 Park, Jung-Heum 2 Patrignani, Maurizio 2 Pivač, Nevena 2 Préville-Ratelle, Louis-François 2 Ramanujan, M. S. 2 Reif, John H. 2 Rutter, Ignaz 2 Stewart, William J. 2 Strehler, Martin 2 Streicher, Manuel 2 Suchan, Karol 2 Voß, Stefan 2 Vušković, Kristina 2 Wiedera, Tilo 2 Yannakakis, Mihalis 1 Aamand, Anders 1 Aboulker, Pierre 1 Addis, Bernardetta 1 Alonso, M. Pilar 1 Anandalingam, G. 1 Andersson, Björn 1 Anjos, Miguel F. 1 Aringhieri, Roberto 1 Ariyoshi, Hiromu 1 Aston, John A. D. 1 Ausiello, Giorgio 1 Baase, Sara 1 Babu, Jasine 1 Bagan, Guillaume 1 Balasundaram, Balabhaskar 1 Bampas, Evangelos 1 Bang-Jensen, Jørgen 1 Bao, Xiaowei 1 Bargiela, Andrzej 1 Basavaraju, Manu 1 Basten, Rob J. I. 1 Batrouni, Ghassan George 1 Beamonte, M. A. 1 Beggas, Fairouz 1 Bei, Xiaohui 1 Bentert, Matthias 1 Berenbrink, Petra 1 Bermond, Jean-Claude 1 Bezáková, Ivona 1 Bilò, Davide 1 Bilò, Vittorio 1 Bixby, Robert E. 1 Bonichon, Nicolas 1 Bonnet, Edouard 1 Boudhar, Mourad 1 Bougeret, Marin 1 Brandstädt, Andreas 1 Briggs, Keith M. 1 Brimkov, Boris 1 Bruckstein, Alfred Marcel 1 Buchanan, Austin 1 Bueno, Lucas Moutinho 1 Cai, Qingpo 1 Cai, Shaowei 1 Caragiannis, Ioannis ...and 297 more Authors all top 5 Cited in 70 Serials 14 Discrete Applied Mathematics 10 Theoretical Computer Science 10 Algorithmica 8 SIAM Journal on Discrete Mathematics 5 Journal of Computer and System Sciences 5 SIAM Journal on Computing 5 Journal of Graph Algorithms and Applications 4 Information Processing Letters 4 Computers & Operations Research 3 Discrete Mathematics 3 Mathematics of Operations Research 3 Computational Geometry 3 The Journal of Artificial Intelligence Research (JAIR) 3 Mathematical Programming Computation 2 Journal of the Association for Computing Machinery 2 Journal of Graph Theory 2 Networks 2 Operations Research 2 Journal of Algorithms 2 Optimization 2 Computing Surveys 2 Computational Optimization and Applications 2 Annals of Mathematics and Artificial Intelligence 2 INFORMS Journal on Computing 2 Fundamenta Informaticae 2 BIT. Nordisk Tidskrift for Informationsbehandling 2 Electronic Journal of Graph Theory and Applications 1 Acta Informatica 1 Artificial Intelligence 1 Journal of the Franklin Institute 1 Journal of Statistical Physics 1 Mathematical Biosciences 1 Applied Mathematics and Computation 1 Information Sciences 1 Journal of Combinatorial Theory. Series B 1 Management Science 1 Monatshefte für Mathematik 1 European Journal of Combinatorics 1 Discrete & Computational Geometry 1 Journal of Automated Reasoning 1 Annals of Operations Research 1 Real-Time Systems 1 International Journal of Computational Geometry & Applications 1 International Journal of Algebra and Computation 1 Games and Economic Behavior 1 ORSA Journal on Computing 1 Aequationes Mathematicae 1 European Journal of Operational Research 1 IEE Proceedings. Part D. Control Theory and Applications 1 Computational Statistics and Data Analysis 1 Experimental Mathematics 1 Combinatorics, Probability and Computing 1 Bernoulli 1 Journal of Heuristics 1 Journal of Combinatorial Optimization 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Data Mining and Knowledge Discovery 1 Methodology and Computing in Applied Probability 1 Foundations of Computational Mathematics 1 Journal of Machine Learning Research (JMLR) 1 Natural Computing 1 Quantum Information Processing 1 Applicable Analysis and Discrete Mathematics 1 The Annals of Applied Statistics 1 Journal of Theoretical Biology 1 Bayesian Analysis 1 EURO Journal on Computational Optimization 1 Other Titles in Applied Mathematics 1 SIAM Journal on Applied Algebra and Geometry 1 Algebraic Combinatorics all top 5 Cited in 22 Fields 98 Combinatorics (05-XX) 98 Computer science (68-XX) 37 Operations research, mathematical programming (90-XX) 7 Statistics (62-XX) 6 Probability theory and stochastic processes (60-XX) 6 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Information and communication theory, circuits (94-XX) 5 Numerical analysis (65-XX) 4 Biology and other natural sciences (92-XX) 2 Group theory and generalizations (20-XX) 2 Convex and discrete geometry (52-XX) 2 Manifolds and cell complexes (57-XX) 1 General and overarching topics; collections (00-XX) 1 Mathematical logic and foundations (03-XX) 1 Number theory (11-XX) 1 Commutative algebra (13-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Associative rings and algebras (16-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Quantum theory (81-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Systems theory; control (93-XX) Citations by Year