{"entities":{"Q4254865":{"pageid":6284466,"ns":120,"title":"Item:Q4254865","lastrevid":108474668,"modified":"2026-11-06T14:57:27Z","type":"item","id":"Q4254865","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1312888"}},"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":"Q4254865$8B567EEB-03F2-47C0-AE9D-2DCF769B2AF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"998bde614ea8e134843bc4b8d1b7eff0bab48800","datavalue":{"value":"1039.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254865$C471A54D-97A9-479E-933A-0BC4A0E58A32","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37911a3f5ceda7e2643e3f01bf4a84c45862a3c9","datavalue":{"value":{"entity-type":"item","numeric-id":2389656,"id":"Q2389656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4254865$F6B9532F-B3F8-46F5-AC5D-DF2D5A521D40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d38e53adff89f3b423353584daf8950b172977c","datavalue":{"value":{"time":"+1999-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":"Q4254865$558723E7-E9E7-471D-B513-8B5206ACB489","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254865$1C952FE6-5F2A-4600-BC92-25BBE07A8D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254865$D5E34B1A-8607-4E30-BA52-86BF3DA4C5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254865$51F8F8F3-AA25-46BA-81BE-A1FA60EB8A39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0406d366322a9954b72d34da315ead2445603f8","datavalue":{"value":"1312888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254865$7810158D-098C-48F9-B2BD-942972FBD3FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4254865$B46E5033-DD39-4198-BFB7-96FF37B7FE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec3505d4a1a47ba6779c1bc97acbae985df00be0","datavalue":{"value":"isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q4254865$EADA79A1-79A4-4379-AFDC-3FFD246F04F6","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":"Q4254865$B1871F8E-E94E-4FAD-8136-87BF94710BBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6307628fe9c2dd0927e6f74057adbb4cbcbabcab","datavalue":{"value":{"entity-type":"item","numeric-id":1428967,"id":"Q1428967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f739704604066ffe037d994d58e6a963e5ae621","datavalue":{"value":{"amount":"+0.91817164","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":"Q4254865$201F483C-2FC5-4827-BD75-C98588F309FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb1ffb2488c557416a2c9adbfbd51cf86b858b3d","datavalue":{"value":{"entity-type":"item","numeric-id":5069657,"id":"Q5069657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce496d7a8072710c663f04c2dace1fdd552a73c6","datavalue":{"value":{"amount":"+0.90713054","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":"Q4254865$ACF02E5C-6F0F-424E-AB31-C5ADD9A63C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3863ece9642cec65f0700e37c2983a63ddbdbfce","datavalue":{"value":{"entity-type":"item","numeric-id":4248537,"id":"Q4248537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39a32f69513ab38a14f5b543d67bf2d54907f32f","datavalue":{"value":{"amount":"+0.9033746","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":"Q4254865$4E58F474-8A32-481D-9572-00747FA171FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e022adceeccaa3c20320b7e7aa19f44bac7948","datavalue":{"value":{"entity-type":"item","numeric-id":4847366,"id":"Q4847366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0683425596cf5e9c128ef7590f9bb70cb08f8b4","datavalue":{"value":{"amount":"+0.8997071","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":"Q4254865$42CF073B-E10F-4B7E-B809-58AB47BA0973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a929e682bc117ba375db7df810d68de6e37124e","datavalue":{"value":{"entity-type":"item","numeric-id":4281643,"id":"Q4281643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a82b05b1291f18560b1f92a76311282536b22e51","datavalue":{"value":{"amount":"+0.89887196","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":"Q4254865$7D3E762E-24AB-4898-9AA1-A1D0CB4EF12C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74d8ae4418494549fc9561bc21f19e211b578396","datavalue":{"value":{"entity-type":"item","numeric-id":1392556,"id":"Q1392556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a596767e2263b5e919bfbf0249daf83d384ba588","datavalue":{"value":{"amount":"+0.89447534","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":"Q4254865$568F8158-89FE-4E90-8A09-836A152CA2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"366c09c0ed88b7834220787c793a8a37c493b308","datavalue":{"value":{"entity-type":"item","numeric-id":3455031,"id":"Q3455031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"822766576fc813374cbb0cda56742223e5730d96","datavalue":{"value":{"amount":"+0.8882106","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":"Q4254865$3A263AD7-805B-4638-AE8E-5C07ADFDC067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f07023917195aa7becc1d79db37341d9ee8c2c11","datavalue":{"value":{"entity-type":"item","numeric-id":1971221,"id":"Q1971221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e6d5fc0a1f799fa74a670976b8f35f803311c6","datavalue":{"value":{"amount":"+0.88473266","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":"Q4254865$20BA3F97-A284-4F98-B74C-8C0DB9A4CBBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb5a63dc210986a2b02c2c6ee1a0b53dd661cda4","datavalue":{"value":{"entity-type":"item","numeric-id":383685,"id":"Q383685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eaad93e755bc8408931f0c60fda43653f000644","datavalue":{"value":{"amount":"+0.87876964","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":"Q4254865$89676CC5-408B-4F40-9B68-A7174DB3FBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91e28c653bcfe51ce03bb3252222eea4f27c9472","datavalue":{"value":{"entity-type":"item","numeric-id":4373667,"id":"Q4373667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a0a88572e47a9c8d4ae5b43f93c497546b6d37f","datavalue":{"value":{"amount":"+0.87690735","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":"Q4254865$91115BAC-EEAC-4DF9-AAC8-8F746B84AC64","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a36cb25c9df36cf6bc808657808b9d1899d38aa","datavalue":{"value":"Aus der Einleitung der Dissertation: Die vorliegende Arbeit ist in zwei Teile gegliedert. Der erste Teil umfa\u00dft die Kapitel 1 und 2. Er beinhaltet als zentrales Ergebnis in Abschnitt 2.3 einen linearen Algorithmus f\u00fcr die homogene Dekomposition. Dieser Algorithmus baut auf den bekannten linearen Algorithmen f\u00fcr die modulare Dekomposition auf. Kapitel 1 enth\u00e4lt die grundlegenden Definitionen und trifft die Vorbereitungen f\u00fcr das Verst\u00e4ndnis des Unterschieds zwischen homogener Dekomposition und modularer Dekomposition. In Abschnitt 2.1 wird dann gezeigt, dass sich eine Vorstufe der homogenen Dekomposition, die wir als medievale Dekomposition bezeichnen, nur unwesentlich von der modularen Dekomposition unterscheidet. Grundlage f\u00fcr die lineare homogene Dekomposition ist die Anwendung eines Satzes \u00fcber Splitgraphen von Hammer und Simeone. In Abschnitt 2.2 ist eine Prozedur angegeben, die es uns erm\u00f6glicht, diesen Satz auf das Ergebnis der Algorithmen zur modularen Dekomposition anzuwenden. Man beachte, dass wir mit der homogenen Dekomposition eines Graphen \\(G\\) unmittelbar die die \\(p\\)-Zusammenhangskomponenten von \\(G\\) erhalten. Folglich ist auch das Berechnen der \\(p\\)-Zusammenhangskomponenten eines beliebigen Graphen in Linearzeit m\u00f6glich. Aus diesem Grund verallgemeinert unser Algorithmus die bisher bekannten linearen Erkennungsalgorithmen f\u00fcr Kographen, \\(P_4\\)-reducible, \\(P_4\\)-sparse und \\(P_4\\)-extendible Graphen. Au\u00dferdem ist er die Grundlage der oben erw\u00e4hnten linearen Algorithmen f\u00fcr Probleme auf \\((q,q-4)\\)- und \\((q,q-3)\\)-Graphen. Im zweiten Teil der Arbeit besch\u00e4ftigen wir uns mit Graphen, die wenige induzierte \\(P_4\\)s enthalten, insbesondere mit den \\((q,q-2)\\)-Graphen f\u00fcr \\(q\\geq 8\\). Dabei ist zu beachten, dass nach Babel f\u00fcr \\((q,q-2)\\)-Graphen mit \\(q\\leq 7\\) das Isomorphieproblem polynomial-\u00e4quivalent zum allgemeinen Isomorphieproblem ist. Daher ist nicht zu erwarten, dass die \\(p\\)-Zusammenhangskomponenten von \\((q,q-2)\\)-Graphen f\u00fcr \\(q\\leq 7\\) eine einfache Struktur haben. Kapitel 3 liefert eine \u00dcbersicht \u00fcber alle bisher untersuchten Graphen mit wenigen \\(P_4\\)s. In Abschnitt 3.5 wird gezeigt, dass die \\(p\\)-Zusammenhangskomponenten von \\((q,q-2)\\)-Graphen mit \\(q\\geq 8\\), bis auf \\(p\\)-Komponenten mit weniger als \\(q\\) Knoten, \\((8,6)\\)-Graphen sind. In Kapitel 4 wird dann eine vollst\u00e4ndige Charakterisierung der \\(p\\)-zusammenh\u00e4ngenden \\((8,6)\\)-Graphen mit mindestens 8 Knoten durchgef\u00fchrt. Dies wird durch eine sehr umfangreiche Fallunterscheidung nach gewissen induzierten Teilgraphen erreicht. Diese Teilgraphen sind die sehnenlosen Kreise mit mehr als 8 Knoten und deren Komplemente, spezielle sogenannte einfache \\(p\\)-Ketten und gewisse einfach strukturierte Splitgraphen, die man als Spider bezeichnet. Im abschlie\u00dfenden Kapitel 5 wird schlie\u00dflich gezeigt, dass die Erkennung, das Testen von Isomorphie, sowie das L\u00f6sen der Standardoptimierungsprobleme f\u00fcr \\((8,6)\\)-Graphen mit linearem Zeitaufwand m\u00f6glich ist. Da die \\((8,6)\\)-Graphen die Kographen, die \\(P_4\\)-reducible, die \\(P_4\\)-lite und die \\(P_4\\)-extendible, die \\(P_4\\)-sparse, die \\(P_4\\)-tidy Graphen sowie die \\(p\\)-B\u00e4ume enthalten, verallgemeinert diese Arbeit viele der angesprochenen Ergebnisse.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4254865$C0AD10F4-7729-40DA-B234-E6FCD04B4490","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4254865","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4254865"}}}}}