Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Source
Material
Years
Person/Organisation
Keywords
  • 1
    Electronic Resource
    Electronic Resource
    An optimal lower bound on the number of variables for graph identification (1992)
    Springer
    Combinatorica 12 (1992), S. 389-410 
    Details
    ISSN: 1439-6912
    Keywords: 03 B 10 ; 05 C 60 ; 05 C 85
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we show that Ω(n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k−1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01305232
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Book
    Book
    Descriptive complexity (1999)
    New York u. a. :Springer,
    Details
    Title: Descriptive complexity
    Author: Immerman, Neil
    Publisher: New York u. a. :Springer,
    Year of publication: 1999
    Pages: 268 S.
    Series Statement: Graduate texts in computer science
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...