Zum Inhalt

Erweiterte Suche

Ergebnisvorschau für Ihre aktuellen Suchbegriffe: 0

Suchoperatoren:

Sie können Operatoren mit Ihrer Suchanfrage kombinieren, um diese noch präziser einzugrenzen. Klicken Sie auf den Suchoperator, um eine Erklärung seiner Funktionsweise anzuzeigen.
Findet Dokumente mit genau dieser Wortgruppe in exakt dieser Schreibweise und Reihenfolge (z.B. "employer branding").
Findet Dokumente, in denen beide Begriffe zusammen vorkommen (z.B. vertrieb UND bonus).
Findet Dokumente, in denen einer der beiden oder beide Begriffe vorkommen (z.B. porsche OR volkswagen).
Findet Dokumente, in denen alle Begriffe vorkommen. Das Leerzeichen wird als UND interpretiert (z.B. mensch roboter alltag).
Findet Dokumente, in denen der Begriff nach NOT nicht vorkommt (z.B. ford NOT "harrison ford").
Findet Dokumente, in denen der gesuchte Begriff mehr als n mal vorkommt. n steht für eine beliebige Anzahl (z.B. COUNT(getriebe)>8).
Findet Dokumente, in denen beide Begriffe in beliebiger Reihenfolge innerhalb von maximal n Worten zueinander stehen. Empfehlung: Wählen Sie zwischen 15 und 30 als maximale Wortanzahl (z.B. NEAR(hybrid, antrieb, 20)).
Findet Dokumente, in denen der Begriff in Wortvarianten vorkommt, wobei diese VOR, HINTER oder VOR und HINTER dem Suchbegriff anschließen können (z.B., leichtbau*, *leichtbau, *leichtbau*).
Findet Dokumente mit dem Suchbegriff in verschiedenen Schreibweisen. Das ? steht für eine einzige Stelle (z.B. organi?ation).
Sonderzeichen werden als UND interpretiert (z.B. Mann + Hummel).

Semantische Suche

powered by (Link öffnet in neuem Fenster)
loading …
Anmelden
Nach oben

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

  • 2021
  • OriginalPaper
  • Buchkapitel
Erschienen in:
Verfasst von
Barnaby Martin
Daniël Paulusma
Siani Smith
Erschienen in
Algorithms and Complexity
Verlag
Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Das Kapitel behandelt das gut untersuchte Thema der Grapheneinfärbung in der Informatik, wobei der Schwerpunkt auf dem 3-Farben-Problem für Graphen mit begrenztem Durchmesser liegt. Es untersucht die Komplexität dieses Problems für verschiedene spezielle Graphenklassen, insbesondere solche, die durch das Fehlen kleiner Zyklen gekennzeichnet sind. Die Autoren präsentieren eine Langzeitstudie zur Komplexität von 3-Färbungen für spezielle Graphenklassen, einschließlich erblicher Graphenklassen. Sie führen ein allgemeineres Problem ein, die Liste 3-Färbung, und beweisen die Lösbarkeit der Polynomzeit für bestimmte Graphenklassen anhand eines einheitlichen Rahmenwerks von Vermehrungsregeln. Das Kapitel hebt die Verwendung von Durchmesser-2-Eigenschaften hervor, um eine weitverbreitete Reduzierung der Listengröße zu gewährleisten, wodurch Instanzen in 2-Listen-Färbungsprobleme umgewandelt werden. Die Autoren stellen auch offene Probleme und zukünftige Forschungsrichtungen in diesem Bereich vor.
KI-Generiert

Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.

Research supported by the Leverhulme Trust (RPG-2016-258).

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Jetzt einloggen Kostenlos registrieren

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Can Local Optimality Be Used for Efficient Data Reduction?
Nächstes Kapitel Online Two-Dimensional Vector Packing With Advice
Titel
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
Verfasst von
Barnaby Martin
Daniël Paulusma
Siani Smith
Copyright-Jahr
2021
Buch
Algorithms and Complexity

Print ISBN: 978-3-030-75241-5

Electronic ISBN: 978-3-030-75242-2

Copyright-Jahr: 2021

DOI
https://doi.org/10.1007/978-3-030-75242-2_26
Dieser Inhalt ist nur sichtbar, wenn du eingeloggt bist und die entsprechende Berechtigung hast.