Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Capture Time of Cops and Robbers Game on a Planar Graph Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Convex Independence in Permutation Graphs

verfasst von : Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

A set C of vertices of a graph is \(P_3\)-convex if every vertex outside C has at most one neighbor in C. The convex hull \(\sigma (A)\) of a set A is the smallest \(P_3\)-convex set that contains A. A set M is convexly independent if for every vertex \(x \in M\), \(x \notin \sigma (M-x)\). We show that the maximal number of vertices that a convexly independent set in a permutation graph can have, can be computed in polynomial time. (Due to space limit, the missing proofs are presented in the full paper. Please see https://​drive.​google.​com/​file/​d/​0B1Ilu0-p1dDsSkpsZFZsR1Y​4Uk0/​view or http://​arxiv.​org/​abs/​1609.​02657).

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 Solving Dynamic Vehicle Routing Problem with Soft Time Window by iLNS and hPSO
Nächstes Kapitel The Connected p-Center Problem on Cactus Graphs
Fußnoten
1
In his classic paper, Duchet defines a graph convexity as a collection of ‘convex’ subsets of a (finite) set V that contains \(\varnothing \) and V, and that is closed under intersections, and that, furthermore, has the property that each convex subset induces a connected subgraph. This last condition is, here, omitted.
 
2
Ramos et al. call it the ‘rank’ of the graph, but this word has been used for so many different concepts that it has lost all meaning.
 
3
Duchet proved that, for interval convexities, the Carathéodory number is the smallest integer \(k \in \mathbb {N}\) such that every \((k+1)\)-set is redundant. Thus, the fixed-parameter Carathéodory number is polynomial.
 
Literatur
1.
2.
Barbosa, R., Coelho, E., Dourado, M., Rautenbach, D., Szwarcfiter, J.: On the Carathéodory number for the convexity of paths of order three. SIAM J. Discrete Math. 27, 929–939 (2012)MathSciNetCrossRefMATH
3.
4.
Borie, R., Parker, R., Tovey, C.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555–581 (1992)MathSciNetCrossRefMATH
5.
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12–75 (1990)MathSciNetCrossRefMATH
6.
Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Klee, V., (ed.) Convexity, Proceedings of the 7th Symposium in Pure Mathematics held at the University of Washington, Seattle, Washington June 13–15, 1961, pp. 101–180. American Mathematical Society (1963)
7.
Dreyer, P., Roberts, F.: Irreversible \(k\)-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math. 157, 1615–1627 (2009)MathSciNetCrossRefMATH
8.
9.
10.
11.
12.
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)CrossRef
13.
Kloks, T., Wang, Y.: Advances in Graph Algorithms. Manuscript on ViXra: 1409.0165 (2014)
14.
Ramos, I., dos Santos, V., Szwarcfiter, J.: Complexity aspects of the computation of the rank of a graph. Discrete Math. Theoret. Comput. Sci. 16, 73–86 (2014)MathSciNetMATH
Metadaten
Titel
Convex Independence in Permutation Graphs
verfasst von
Wing-Kai Hon
Ton Kloks
Fu-Hong Liu
Hsiang-Hsuan Liu
Copyright-Jahr
2016
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-48749-6_52