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:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling

verfasst von : Amihood Amir, Benny Porat

Erschienen in: Combinatorial Pattern Matching

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measure is the minimum number of label swaps necessary to transform the graph from one labeling to the other, where a swap is the interchange of the labels of two adjacent nodes. We are interested in the complexity of determining the swap distance. The problem has been recently explored for various restricted classes of graphs, but its complexity in general graphs has not been established.
We show that the problem is \(\mathcal {NP}\)-hard. In addition we consider restricted versions of the problem where a node can only participate in a bounded number of swaps. We show that the problem is \(\mathcal {NP}\)-hard under these restrictions as well.

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
Nächstes Kapitel A Framework for Space-Efficient String Kernels
Literatur
1.
Agnarsson, G., Greenlaw, R., Kantabutra, S.: On the graph relabeling problem. Thai J. Math. 8(1), 21–42 (2010)MATHMathSciNet
2.
Akutsu, T.: A linear time pattern matching algorithm between a string and a tree. In: Proceedings of 4th Symposium on Combinatorial Pattern Matching (CPM), pp. 1–10, Padova (1993)
3.
Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \(\ell _{1}\) and \(\ell _{\infty }\) rearrangement distances. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 39–49. Springer, Heidelberg (2007) CrossRef
4.
5.
Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances. In: Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1221–1229 (2006)
6.
Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 118–129. Springer, Heidelberg (2008) CrossRef
7.
Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. In: Proceedings of 38th IEEE FOCS, pp. 144–153 (1997)
8.
Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. J. Algorithms 37(2), 247–266 (2000). (Preliminary version appeared at FOCS 1997)MATHMathSciNetCrossRef
9.
10.
11.
Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. SIAM J. Comp. 39(4), 1444–1461 (2009)MATHMathSciNetCrossRef
12.
Amir, A., Landau, G.M., Lewenstein, M., Lewenstein, N.: Efficient special cases of pattern matching with swaps. Inf. Process. Lett. 68(3), 125–132 (1998)MathSciNetCrossRef
13.
14.
15.
16.
Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: From coding theory to efficient pattern matching. In: Proceedings of 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 778–784 (2009)
17.
Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: k-Mismatch with don’t cares. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 151–162. Springer, Heidelberg (2007) CrossRef
18.
Clifford, R., Porat, E.: A Filtering algorithm for k-mismatch with don’t cares. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 130–136. Springer, Heidelberg (2007) CrossRef
19.
Cole, R., Hariharan, R.: Randomized swap matching in \(o(m \log m \log |\sigma |)\) time. Technical report TR1999-789, New York University, Courant Institute, September 1999
20.
Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: A faster implementation of the goemans-williamson clustering algorithm. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 17–25 (2001)
21.
Dombb, Y., Lipsky, O., Porat, B., Porat, E., Tsur, A.: Approximate swap and mismatch edit distance. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 149–163. Springer, Heidelberg (2007) CrossRef
22.
Duato, J.: A theory of fault-tolerant routing in wormhole networks. IEEE Trans. Parallel Distrib. Syst. 8(8), 790–802 (1997)CrossRef
23.
24.
Gallian, J.A.: A dynamic survey of graph labeling. Electronic Journal of Combinatorics 18, 1–219 (2011)
25.
26.
27.
Johnson, W.W., Woolsay, W.E.: Notes on the ‘15 puzzle’. Am. J. Math. 2(4), 397–404 (1879)MATHCrossRef
28.
Kantabutra, S.: The complexity of label relocation problems on graphs. In: Proceedings of 8th Asian Symposium of Computer Mathematics, National University of Singapore (2007)
29.
Kapah, O., Landau, G.M., Levy, A., Oz, N.: Interchange rearrangement: the element-cost model. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 224–235. Springer, Heidelberg (2008) CrossRef
30.
Kim, D.K., Park, K.: String matching in hypertext. In: Proceedings of 6th Symposium on Combinatorial Pattern Matching (CPM 1995) (1995)
31.
Lipsky, O., Porat, B., Porat, E., Shalom, B.R., Tzur, A.: Approximate string matching with swap and mismatch. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 869–880. Springer, Heidelberg (2007) CrossRef
32.
Manber, U., Wu, S.: Approximate string matching with arbitrary cost for text and hypertext. In: Proceedings International Workshop on Structural and Syntactic Pattern Recognition, pp. 22–33 (1992)
33.
Muir, T.: A treatise of the thoery of determinants with graduated sets of exercises. Macmillan and Co., London (1882)
34.
Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Zvi, Ukkonen, Esko (eds.) CPM 1995. LNCS, vol. 937, pp. 298–317. Springer, Heidelberg (1995) CrossRef
35.
Metadaten
Titel
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
verfasst von
Amihood Amir
Benny Porat
Copyright-Jahr
2015
Buch
Combinatorial Pattern Matching

Print ISBN: 978-3-319-19928-3

Electronic ISBN: 978-3-319-19929-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19929-0_1