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:
Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Linear MIM-Width of Trees

verfasst von : Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We provide an \(O(n \log n)\) algorithm computing the linear maximum induced matching width of a tree and an optimal layout.

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 Geometric Representations of Dichotomous Ordinal Data
Nächstes Kapitel Approximating Minimum Dominating Set on String Graphs
Literatur
1.
Adler, I., Kanté, M.M.: Linear rank-width and linear clique-width of trees. Theor. Comput. Sci. 589, 87–98 (2015)MathSciNetCrossRef
2.
Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54–65 (2013)MathSciNetCrossRef
3.
Bergougnoux, B., Kanté, M.M.: Rank based approach on graphs with structured neighborhood. CoRR, abs/1805.11275 (2018)
4.
Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66–76 (2013)MathSciNetCrossRef
5.
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)MATH
6.
Ellis, J.A., Sudborough, I.H., Turner, J.S.: The vertex separation and search number of a graph. Inf. Comput. 113(1), 50–79 (1994)MathSciNetCrossRef
7.
Fomin, F.V., Golovach, P.A., Raymond, J.-F.: On the tractability of optimization problems on H-graphs. In: Proceedings of the ESA 2018, pp. 30:1–30:14 (2018)
8.
Galby, E., Munaro, A., Ries, B.: Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded MIM-width. CoRR, abs/1810.06872 (2018)
9.
Golovach, P.A., Heggernes, P., Kanté, M.M., Kratsch, D., Sæther, S.H., Villanger, Y.: Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica 80(2), 714–741 (2018)MathSciNetCrossRef
10.
Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000)MathSciNetCrossRef
11.
Hlinený, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2008)CrossRef
12.
13.
Jaffke, L., Kwon, O., Strømme, T.J.F., Telle, J.A.: Generalized distance domination problems and their complexity on graphs of bounded MIM-width. In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, Helsinki, Finland, 20–24 August 2018, pp. 6:1–6:14 (2018)
14.
Jaffke, L., Kwon, O., Telle, J.A.: Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded MIM-width. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Vienna, Austria, 6–8 September 2017, pp. 21:1–21:13 (2017)
15.
Jaffke, L., Kwon, O., Telle, J.A.: A unified polynomial-time algorithm for feedback vertex set on graphs of bounded MIM-width. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, Caen, France, 28 February–3 March 2018, pp. 42:1–42:14 (2018)
16.
17.
18.
19.
Sæther, S.H., Vatshelle, M.: Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci. 615, 120–125 (2016)MathSciNetCrossRef
20.
Skodinis, K.: Construction of linear tree-layouts which are optimal with espect to vertex separation in linear time. J. Algorithms 47(1), 40–59 (2003)MathSciNetCrossRef
21.
Vatshelle, M.: New width parameters of graphs. Ph.D. thesis, University of Bergen, Norway (2012)
22.
Yamazaki, K.: Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms 11(11), 173 (2018)MathSciNetCrossRef
Metadaten
Titel
Linear MIM-Width of Trees
verfasst von
Svein Høgemo
Jan Arne Telle
Erlend Raa Vågset
Copyright-Jahr
2019
Buch
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-30786-8_17