| Property |
Value |
| dbo:abstract
|
- Babai László (Budapest, 1950. július 20. –) magyar matematikus, egyetemi tanár, a Magyar Tudományos Akadémia rendes tagja. A kombinatorika, a csoportelmélet neves kutatója. (hu)
- Babai László (Budapest, 1950. július 20. –) magyar matematikus, egyetemi tanár, a Magyar Tudományos Akadémia rendes tagja. A kombinatorika, a csoportelmélet neves kutatója. (hu)
|
| dbo:citizenship
| |
| dbo:occupation
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10352 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| prop-hu:content
|
- We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism and Coset Intersection can be solved in quasipolynomial time. The best previous bound for GI was where is the number of vertices ; for the other two problems, the bound was similar, where is the size of the permutation domain . (hu)
- The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic «local certificates» and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. (hu)
- We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism and Coset Intersection can be solved in quasipolynomial time. The best previous bound for GI was where is the number of vertices ; for the other two problems, the bound was similar, where is the size of the permutation domain . (hu)
- The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic «local certificates» and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. (hu)
|
| prop-hu:header
|
- Absztrakt (hu)
- Absztrakt (hu)
|
| prop-hu:kép
|
- LaszloBabai.JPG (hu)
- LaszloBabai.JPG (hu)
|
| prop-hu:képaláírás
|
- Babai László egy konferencián 2013-ban (hu)
- Babai László egy konferencián 2013-ban (hu)
|
| prop-hu:nemzetiség
| |
| prop-hu:név
|
- Babai László (hu)
- Babai László (hu)
|
| prop-hu:szakma
|
- egyetemi tanár (hu)
- matematikus, (hu)
- egyetemi tanár (hu)
- matematikus, (hu)
|
| prop-hu:születésiDátum
| |
| prop-hu:születésiHely
| |
| prop-hu:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:label
|
- Babai László (hu)
- Babai László (hu)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
