{"entities":{"Q4409148":{"pageid":6438747,"ns":120,"title":"Item:Q4409148","lastrevid":109083071,"modified":"2026-11-11T10:46:49Z","type":"item","id":"Q4409148","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1942448"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4409148$5943154B-85A2-407A-8C76-B30F7C7099F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4c630b3aef1cb3c9d26398d6801c5e20280a105a","datavalue":{"value":"1031.68089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4409148$46FBAA7D-0A30-4FCE-9192-36038BC9F306","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0f37edc6c8f52ba2382087ad0ad81d355970e4f","datavalue":{"value":{"entity-type":"item","numeric-id":4409147,"id":"Q4409147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4409148$DFF3F545-F377-42F4-A958-3B4CEE6925E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7b4101504a6d0e37a5946d6cb9fc5f2100ad9f87","datavalue":{"value":{"time":"+2003-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4409148$57B12704-C80D-4B32-A1D5-A07B92DE7026","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8b21c00f25ef9dafe82f385422f402059a0bd183","datavalue":{"value":"http://d-nb.info/960091637","type":"string"},"datatype":"url"},"type":"statement","id":"Q4409148$4A072687-A433-4754-8ECF-056DF808E01E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4409148$9434AB83-8E23-4F35-952F-F7DB481043C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4409148$73CBF63D-C857-441D-805E-91DCBE7C0B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4409148$60D7A2E1-6FDF-43D7-A568-EBDDF721E685","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6feeaa24c4fcf40253240a211771c3df4bb6def8","datavalue":{"value":"1942448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4409148$B8A0A062-D233-480B-BDB6-FD26EEA04CDA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80c99afc4950f85b79a2fe3707eb2e870b9567f","datavalue":{"value":"separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4409148$6AC0F4BF-4519-44A7-B6E3-DCB8BB05DEDF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4409148$9F0CF1A6-DA59-48AA-A6D1-18ACF30326B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f480f862f813079c75f91e79bfdbdf05621708f","datavalue":{"value":{"entity-type":"item","numeric-id":1098301,"id":"Q1098301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a918c7d1493e28fc7deec2ac80478f166fd5ada","datavalue":{"value":{"amount":"+0.9056207","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$8BF776CF-3555-4C45-BF05-273329F38536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ed3787190bba34cde307c7c4c7d7a7e495bced","datavalue":{"value":{"entity-type":"item","numeric-id":4862886,"id":"Q4862886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c21336fa8b99ed2caca13ca06ba9b1c4ed3ad4d8","datavalue":{"value":{"amount":"+0.88529694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$51B6A788-FACC-4350-BE60-FF9FA41E8371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a571bd2151c34fd6bd23a286fa02c373188232ca","datavalue":{"value":{"entity-type":"item","numeric-id":2320763,"id":"Q2320763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64d4d9825faf3cbd636b0be69d5b76a0e0a0402e","datavalue":{"value":{"amount":"+0.88385683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$5FB84F40-6B47-4DD9-A412-0309F855DC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1cd4b343f2cb7dd3ddd9ed9640c80eaea768294","datavalue":{"value":{"entity-type":"item","numeric-id":3745869,"id":"Q3745869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"322209792bb08ac0f607856936c85879ac7efc75","datavalue":{"value":{"amount":"+0.88298446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$C6097B5D-FD55-4873-87E0-7341C55C78C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db7c63400b53ae0306760174514d9bcbc2c69dc1","datavalue":{"value":{"entity-type":"item","numeric-id":906255,"id":"Q906255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4f06706e34f6edd879ab7bef33a95603d51da49","datavalue":{"value":{"amount":"+0.86764866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$1CB314A2-1429-4675-A1D6-6B8136155356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755d8d3f09c9e8b1f6d76f6eb207cf218d5a400d","datavalue":{"value":{"entity-type":"item","numeric-id":4889503,"id":"Q4889503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f89040fcd001db6198b7284fe7d93b681410eea","datavalue":{"value":{"amount":"+0.8657583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4409148$9D29FA44-6FF8-4F32-BC0C-03098419D41D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2085180e839737b41cb2f86be1c4b64b4113cfbd","datavalue":{"value":"Zusammenfassung und Ausblick: F\u00fcr B\u00e4ume, kreisfreie Graphen und Graphen, f\u00fcr die innerhalb jeder 2-Zusammenhangskomponente die Online-Entfernungsberechnung in konstanter Laufzeit m\u00f6glich ist, haben wir in Kapitel 5 optimale Werte f\u00fcr \\({\\mathcal S}\\), \\({\\mathcal T}\\) und \\({\\mathcal Q}\\) gezeigt, d.h. eine lineare Preprocessing-Phase gen\u00fcgt, um SPSD in konstanter Laufzeit zu berechnen. In den Kapiteln 6 und 7 haben wir zwei kontr\u00e4re Ans\u00e4tze zur Konstruktion Hierarchischer Graphen untersucht. Geeignete Knotenmenge wie auch die Separatormengen sollten m\u00f6glichst klein sein, jedoch separieren Geeignete Knotenmengen den Graphen i. A. nicht, und Separatormengen sind i. A. keine Geeigneten Knotenmengen. Die Berechnung minimaler Geeigneter Knotenmengen und die Berechnung minimaler Umgebungsabst\u00e4nde haben wir als NP-vollst\u00e4ndig nachgewiesen und eine logarithmische bzw. konstante Approximation (f\u00fcr den Umgebungsabstand) angegeben. Au\u00dferdem haben wir eine Verallgemeinerung Geeigneter Graphen zu teilgeeigneten Graphen definiert und das Eignungskonzept auf Levelgraphen \u00fcbertragen. In Kapitel 7 haben wir ein rekursives Separationskonzept -- Separatorb\u00e4ume -- eingef\u00fchrt und darauf verschiedene Hierarchische Graphen definiert. Sofern nur ein \\(\\alpha\\)-\\(\\beta\\)-\\(f(n)\\)-Separatorbaum zur Verf\u00fcgung steht, haben wir \\({\\mathcal S}\\in O(n(f(n)+\\log n))\\), \\({\\mathcal T}\\in O((m+ n\\log n)f(n))\\) und \\({\\mathcal Q}\\in O(f(n))\\) nachgewiesen. Aus den Separatorb\u00e4umen haben wir die Separatorweite als einen neuen charakteristischen Parameter eines Graphen abgeleitet und gezeigt, dass sie i. A. von der Baumweite verschieden ist und h\u00f6chstens um einen logarithmischen Faktor von der Baumweite abweicht. Hier ist die These naheliegend, dass einige i.A. NP-vollst\u00e4ndige Probleme f\u00fcr Graphen mit konstanter Separatorweite ebenso wie f\u00fcr Graphen mit konstanter Baumweite in \\(P\\) liegen. Dies ist noch zu pr\u00fcfen. F\u00fcr planare Graphen konnten wir mittels sogenannter D\u00fcnner-Trennender-Hierarchischer-Graphen zeigen, dass fast ein linearer Speicherplatz gen\u00fcgt, um \\({\\mathcal Q}\\in\\widetilde O(\\sqrt{n})\\) zu gew\u00e4hrleisten. Das Konzept der Separation eignet sich auch f\u00fcr Approximationen. F\u00fcr beliebige Graphen kann auf fast linearem Platz ein Einfacher-Trennender-Hierarchischer-Graph berechnet werden, so dass online die Entfernung in fast konstanter Laufzeit approximiert wird. F\u00fcr beide untersuchten Ans\u00e4tze zur Konstruktion Hierarchischer Graphen haben sich weitere Fragestellungen ergeben. F\u00fcr Geeignete Graphen sollte insbesondere das Kriterium f\u00fcr die Umgebungsgr\u00f6\u00dfe variiert werden. Um dabei auch konkrete Werte f\u00fcr \\({\\mathcal S}\\), \\({\\mathcal T}\\) und \\({\\mathcal Q}\\) in der \\(O\\)-Notation zu erhalten, muss das Eignungskonzept auf spezielle Graphklassen, \u00e4hnlich den \\(k\\)-Levelgittergraphen in Abschnitt 6.6.1, angewendet werden. Der Ansatz der rekursiven Separation l\u00e4sst sich eventuell dadurch verbessern, dass man Separationen nur bez\u00fcglich der k\u00fcrzesten Wege betrachtet, d.h. man \u00e4ndert in der Definition 10 die Gleichung 7.1 zu: \\[ \\forall_{u\\in X_1} \\forall_{v\\in X_2} \\forall_{w\\in SP(u,v)}\\qquad V(w)\\cap Y\\neq\\emptyset. \\] Hier ben\u00f6tigt man dann ein neues Separationsverfahren \u00e4hnlich dem von Lipton und Tarjan, das wir in dieser Arbeit benutzt haben. Interessant ist au\u00dferdem, ob sich das Konzept der DTHG auch auf andere nichtplanare Graphen adaptieren l\u00e4sst. Kombinationen der beiden Hierarchiekonzepte und die Angemessenheit, um dynamische Aspekte von Graphen abzubilden, sollten ebenfalls k\u00fcnftig untersucht werden. Insbesondere im Zusammenhang mit Verkehrsinformationssystemen besteht hier ein gro\u00dfer Bedarf. Aus theoretischer Sicht sind die unteren Schranken f\u00fcr die Parameter \\({\\mathcal S}\\), \\({\\mathcal T}\\) und \\({\\mathcal Q}\\) i. A. und abh\u00e4ngig von den gegebenen Graphen zu untersuchen. Einen Hinweis liefert hier das Resultat \\({\\mathcal S}{\\mathcal Q}\\in\\widetilde O(n^{1.5})\\) f\u00fcr planare Graphen, das modulo logarithmischer Faktoren optimal ist.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4409148$6BF27A55-9158-4BE4-B451-C37BC8EE7CB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4409148","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4409148"}}}}}