Metraipolis › archive › dc_ceceeb106239

Cliquenweite — Wikipedia (de)

Source: Wikipedia (de)
Original: https://de.wikipedia.org/wiki/Cliquenweite
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-03T20:42:09.678Z
SHA-256 of the archived text: 066c040d97541ec0d6baa1f07ea55859aba571f10b837b5cf76740232b30dcfd
Stable URL of this page: https://metraipolis.com/documento/dc_ceceeb106239

How to cite

Cliquenweite — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Cliquenweite (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ceceeb106239 (Metraipolis archive dc_ceceeb106239, sha256 066c040d97541ec0d6baa1f07ea55859aba571f10b837b5cf76740232b30dcfd)

BibTeX

@misc{dcceceeb106239,
  title = {Cliquenweite — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Cliquenweite},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ceceeb106239; sha256 066c040d97541ec0d6baa1f07ea55859aba571f10b837b5cf76740232b30dcfd},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Cliquenweite. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen G = ( V , E ) {\displaystyle G=(V,E)} eine natürliche Zahl zu. Sie ist daher ein Graphparameter. Mit Hilfe eines k-Ausdrucks (s. u.) lassen sich viele NP-vollständige Probleme wie zum Beispiel HAMILTONKREIS oder CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE in Zeit O ( f ( k ) ⋅ n ) {\displaystyle O(f(k)\cdot n)} lösen, was für konstante k {\displaystyle k} eine lineare Laufzeit ist. Da jedoch nicht bekannt ist, ob ein k-Ausdruck hinreichend schnell berechnet werden kann, ist es zur Zeit unklar, ob man hieraus folgern kann, dass diese Probleme auf Graphen mit beschränkter Cliquenweite effizient zu lösen sind.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Cliquenweite» — https://de.wikipedia.org/wiki/Cliquenweite
Wikidata Q1101814: «measure of graph complexity» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1101814
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Cliquenweite?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 253605216, consultata il 2026-11-03T20:33:38.814Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9ebfbf6fdbcf1acdef561423ea1c7b774cc182651b4f01eb4484ec333b95201d