No label defined (Q3971999)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 15355
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 15355 |
Statements
25 June 1992
0 references
NP-complete
0 references
efficient algorithms
0 references
0.7962953448295593
0 references
0.7962953448295593
0 references
0.7670091986656189
0 references
[For the entire collection see Zbl 0698.00017.] It has turned out that almost all natural decision problems on graphs are NP-complete. So it was an obvious question whether the structural properties of special graph classes help to design efficient algorithms when the problems are restricted to these classes. This paper gives a uniform description (so-called FOSG-characterizations) of such well-known graph classes which are usually defined by very different principles (intersection graphs, graphs related to posets, partitions of the vertex set, chordality properties, forbidden subgraphs, etc.).
0 references
