Problem izomorfizma grafova (Serbian Wikipedia)
Analysis of information sources in references of the Wikipedia article "Problem izomorfizma grafova" in Serbian language version.
refsWebsite
Global rank
Serbian rank
11th place
23rd place
5th place
12th place
942nd place
2,000th place
1st place
1st place
1,523rd place
2,120th place
low place
low place
3rd place
2nd place
acm.org
portal.acm.org
- László Babai, William Kantor, Eugene Luks, Computational complexity and the classification of finite simple groups, Proc. 24th FOCS (1983). стр. 162.–171.
dl.acm.org
- Baird, HS; Cho, YE (1975). An artwork design verification system. Proceedings of the 12th Design Automation Conference. IEEE Press. стр. 414—420.
anu.edu.au
cs.anu.edu.au
- McKay 1981 McKay, Brendan D. (1981), „Practical graph isomorphism”, Congressus Numerantium, 30: 45—87, 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980).
arxiv.org
- The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2): 1, S2CID 1658062, arXiv:cs.CG/0601002
, doi:10.1145/1346330.1346336 - Cristopher Moore; Russell, Alexander; Schulman, Leonard J. (2005). „The Symmetric Group Defies Strong Fourier Sampling: Part I”. arXiv:quant-ph/0501056v3 [quant-ph].
books.google.com
- Cook, Diane J.; Holder, Lawrence B. (2006). Mining Graph Data. John Wiley & Sons. стр. 120—122. ISBN 978-0-470-07303-2.
doi.org
- The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2): 1, S2CID 1658062, arXiv:cs.CG/0601002 , doi:10.1145/1346330.1346336
- Johnson 2005 Johnson, David S. (2005), „The NP-Completeness Column”, ACM Transactions on Algorithms, 1 (1): 160—176, S2CID 12604799, doi:10.1145/1077464.1077476. (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.)
- Ullman 1976 Ullman, Julian R. (1976), „An algorithm for subgraph isomorphism”, Journal of the ACM, 23: 31—42, S2CID 17268751, doi:10.1145/321921.321925.
- Hopcroft & Wong 1974 Hopcroft, John; Wong, J. (1974), „Linear time algorithm for isomorphism of planar graphs”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, стр. 172—184, S2CID 15561884, doi:10.1145/800119.803896.
- Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian (2009). „Planar Graph Isomorphism is in Log-Space”. 2009 24th Annual IEEE Conference on Computational Complexity. стр. 203—214. ISBN 978-0-7695-3717-7. doi:10.1109/CCC.2009.16.
- Booth & Lueker 1979 Booth, Kellogg S.; Lueker, George S. (1979), „A linear time algorithm for deciding interval graph isomorphism”, Journal of the ACM, 26 (2): 183—195, S2CID 18859101, doi:10.1145/322123.322125.
- Colbourn 1981 Colbourn, C. J. (1981), „On testing isomorphism of permutation graphs”, Networks, 11: 13—21, doi:10.1002/net.3230110103.
- Bodlaender 1990 Bodlaender, Hans (1990), „Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees”, Journal of Algorithms, 11 (4): 631—643, doi:10.1016/0196-6774(90)90013-5.
- Miller 1980; Filotti & Mayer 1980 Miller, Gary (1980), „Isomorphism testing for graphs of bounded genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 225—235, ISBN 978-0-89791-017-0, S2CID 13647304, doi:10.1145/800141.804670. Filotti, I. S.; Mayer, Jack N. (1980), „A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 236—243, ISBN 978-0-89791-017-0, S2CID 16345164, doi:10.1145/800141.804671.
- Luks 1982 Luks, Eugene M. (1982), „Isomorphism of graphs of bounded valence can be tested in polynomial time”, Journal of Computer and System Sciences, 25: 42—65, doi:10.1016/0022-0000(82)90009-5.
- Köbler, Schöning & Torán 1992; Arvind & Kurur 2006 Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), „Graph isomorphism is low for PP”, Computational Complexity, 2 (4): 301—330, S2CID 8542603, doi:10.1007/BF01200427. Arvind, Vikraman; Kurur, Piyush P. (2006), „Graph isomorphism is in SPP”, Information and Computation, 204 (5): 835—852, doi:10.1016/j.ic.2006.02.002.
- Zemlyachenko, Korneenko & Tyshkevich 1985 Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), „Graph isomorphism problem”, Journal of Mathematical Sciences, 29 (4): 1426—1481, S2CID 121818465, doi:10.1007/BF02104746. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118. (1982). стр. 83–158.)
- Chung, Fan RK (1985). „On the cutwidth and the topological bandwidth of a tree”. SIAM Journal on Algebraic Discrete Methods. 6 (2): 268—277. doi:10.1137/0606026. Приступљено 13. 4. 2015.
- Kozen 1978 Kozen, Dexter (1978), „A clique problem equivalent to graph isomorphism”, ACM SIGACT News, 10 (2): 50—52, S2CID 52835766, doi:10.1145/990524.990529.
- R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson 2005 Johnson, David S. (2005), „The NP-Completeness Column”, ACM Transactions on Algorithms, 1 (1): 160—176, S2CID 12604799, doi:10.1145/1077464.1077476. (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.)
escholarship.org
- Booth & Lueker 1979 Booth, Kellogg S.; Lueker, George S. (1979), „A linear time algorithm for deciding interval graph isomorphism”, Journal of the ACM, 26 (2): 183—195, S2CID 18859101, doi:10.1145/322123.322125.
iitm.ac.in
cse.iitm.ac.in
- "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008). стр. 688-696.
itu.dk
pure.itu.dk
- Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian (2009). „Planar Graph Isomorphism is in Log-Space”. 2009 24th Annual IEEE Conference on Computational Complexity. стр. 203—214. ISBN 978-0-7695-3717-7. doi:10.1109/CCC.2009.16.
semanticscholar.org
api.semanticscholar.org
- The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2): 1, S2CID 1658062, arXiv:cs.CG/0601002 , doi:10.1145/1346330.1346336
- Johnson 2005 Johnson, David S. (2005), „The NP-Completeness Column”, ACM Transactions on Algorithms, 1 (1): 160—176, S2CID 12604799, doi:10.1145/1077464.1077476. (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.)
- Ullman 1976 Ullman, Julian R. (1976), „An algorithm for subgraph isomorphism”, Journal of the ACM, 23: 31—42, S2CID 17268751, doi:10.1145/321921.321925.
- Hopcroft & Wong 1974 Hopcroft, John; Wong, J. (1974), „Linear time algorithm for isomorphism of planar graphs”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, стр. 172—184, S2CID 15561884, doi:10.1145/800119.803896.
- Booth & Lueker 1979 Booth, Kellogg S.; Lueker, George S. (1979), „A linear time algorithm for deciding interval graph isomorphism”, Journal of the ACM, 26 (2): 183—195, S2CID 18859101, doi:10.1145/322123.322125.
- Miller 1980; Filotti & Mayer 1980 Miller, Gary (1980), „Isomorphism testing for graphs of bounded genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 225—235, ISBN 978-0-89791-017-0, S2CID 13647304, doi:10.1145/800141.804670. Filotti, I. S.; Mayer, Jack N. (1980), „A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, стр. 236—243, ISBN 978-0-89791-017-0, S2CID 16345164, doi:10.1145/800141.804671.
- Köbler, Schöning & Torán 1992; Arvind & Kurur 2006 Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), „Graph isomorphism is low for PP”, Computational Complexity, 2 (4): 301—330, S2CID 8542603, doi:10.1007/BF01200427. Arvind, Vikraman; Kurur, Piyush P. (2006), „Graph isomorphism is in SPP”, Information and Computation, 204 (5): 835—852, doi:10.1016/j.ic.2006.02.002.
- Zemlyachenko, Korneenko & Tyshkevich 1985 Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), „Graph isomorphism problem”, Journal of Mathematical Sciences, 29 (4): 1426—1481, S2CID 121818465, doi:10.1007/BF02104746. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118. (1982). стр. 83–158.)
- Kozen 1978 Kozen, Dexter (1978), „A clique problem equivalent to graph isomorphism”, ACM SIGACT News, 10 (2): 50—52, S2CID 52835766, doi:10.1145/990524.990529.
- R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson 2005 Johnson, David S. (2005), „The NP-Completeness Column”, ACM Transactions on Algorithms, 1 (1): 160—176, S2CID 12604799, doi:10.1145/1077464.1077476. (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.)
siam.org
epubs.siam.org
- Chung, Fan RK (1985). „On the cutwidth and the topological bandwidth of a tree”. SIAM Journal on Algebraic Discrete Methods. 6 (2): 268—277. doi:10.1137/0606026. Приступљено 13. 4. 2015.
uconn.edu
engr.uconn.edu
- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism Архивирано на сајту Wayback Machine (24. септембар 2015), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
web.archive.org
- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism Архивирано на сајту Wayback Machine (24. септембар 2015), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
worldcat.org
- Booth & Colbourn 1977; Köbler, Schöning & Torán 1993 Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287.
- Arvind & Köbler 2000 Arvind, Vikraman; Köbler, Johannes (2000), „Graph isomorphism is low for ZPP(NP) and other lowness results.”, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 1770, Springer-Verlag, стр. 431—442, ISBN 978-3-540-67141-1, OCLC 43526888.