Language:   Search:   Contact
World of
Mathematics Database
»ZMATH« MSC 2000
MSC 2010 Reviewer
Service Subscription
»ZMATH«
ZMATH Database | Simple Search Print
Read more | Try MathML | Hide
Zentralblatt MATH has released its new 2010 interface!
For an improved author identification, see the new author database of ZBMATH.

ZMATH Database Simple Search Advanced Search Command Search

Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 0571.05050
Nešetřil, Jaroslav; Poljak, Svatopluk
On the complexity of the subgraph problem. (English)
[J] Commentat. Math. Univ. Carol. 26, 415-419 (1985). ISSN 0010-2628

It is proved that the following problem has the complexity $O(n\sp k):$ For a given graph G with n vertices detect if G contains a fixed subgraph with k vertices.
[W.Zielonka]
MSC 2000:
*05C99 Graph theory
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory in connection with computer science

Keywords: subgraph containment

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Journal Journal

Login Username: Password:

Highlights
Scientific prize winners of the ICM 2010
Overhang
Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Master Server

Zentralblatt MATH Berlin [Germany]

© FIZ Karlsruhe GmbH

Zentralblatt MATH master server is maintained by the Editorial Office in Berlin, Section Mathematics and Computer Science of FIZ Karlsruhe and is updated daily.

Other Mirror Sites

Copyright © 2010 Zentralblatt MATH | European Mathematical Society | FIZ Karlsruhe | Heidelberg Academy of Sciences
Published by Springer-Verlag | Webmaster