{"entities":{"Q1364473":{"pageid":1375212,"ns":120,"title":"Item:Q1364473","lastrevid":46943559,"modified":"2025-12-25T21:55:04Z","type":"item","id":"Q1364473","labels":{"en":{"language":"en","value":"Measuring the vulnerability for classes of intersection graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1057100"}},"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":"Q1364473$442A5F4A-08B4-4075-B857-636EB84FF3AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7dbe7781ad450e9b9a3a2037e360b2ae6baf7af6","datavalue":{"value":{"text":"Measuring the vulnerability for classes of intersection graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1364473$C9D8D8D4-3BA8-4EA1-A155-BA45D92FBAB8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6dea28f3118535585772fd830875d7a908ef8246","datavalue":{"value":"0881.05118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$5FD8F1B2-F5CB-4211-B813-3B1B57D6CF83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"068f72f1244492b760266bc2516ce9caff19712f","datavalue":{"value":"10.1016/S0166-218X(96)00133-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$745D2B85-78D1-469B-8099-6A7354389B67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$8415C4DB-B078-44D2-BA43-3305BBF6DF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8e7715a2f78d23e9e49bdcad66cde6bee1dec62","datavalue":{"value":{"entity-type":"item","numeric-id":190505,"id":"Q190505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$09E35D31-3CB0-495F-98B5-F20D7555E12F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d838f189c5dee0252f326bcac58fa27d9924b24e","datavalue":{"value":{"entity-type":"item","numeric-id":190507,"id":"Q190507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$E35813B1-5E98-41C8-BA5B-186C37FE6A81","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$78375509-5FBF-4B9F-8C24-181D8BFF078E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24fb4fe71a2595983b723d9da5040cfe01165fe6","datavalue":{"value":{"time":"+1998-02-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1364473$E527D6DE-3C9B-4D08-888F-7161172A1750","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1364473$9B8BDF48-33F6-4D40-AF1B-13DC95EE343B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b328dd0011def7d3a76e37b715c002b4187dbb4","datavalue":{"value":"Edge connectivity is a very studied parameter in graph theory which measures the vulnerability of a graph (i.e. the resistance of the graph to deletions of vertices or edges). But there are other parameters of interest. For example, if the binding number of a graph is at least \\(3/2\\), then the existence of a Hamiltonian circuit is guaranted.   In this paper, the authors focus on three previously introduced parameters, namely the thoughness (introduced by Chv\u00e1tal in 1973), the scattering number (introduced by Jung in 1978) and the vertex integrity (introduced by Barefoot in 1987). From an algorithmic point of view, this paper shows that these three parameters can be compared efficiently for many important graph classes.   The minimum balanced separator problem is also considered. The authors exhibit polynomial time algorithms which compute exactly a balanced separator of minimum cardinality for special graphs. The algorithms exhibited here compute component number vectors and maximum component order vectors which give information on the vulnerability of graphs.   In conclusion, the authors detail how the approach developed in this paper for trapezoid graphs can be generalized to other classes of intersection graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$73F7B644-7D25-450C-86F0-82572BEE8041","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$74AD8429-DEE7-4EE0-A98F-D7E9A4FC86FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$71F5996A-12E7-4A16-8DE3-8621FD2BF551","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b8929c06221b0a752e658464d815c57a58d492d","datavalue":{"value":"1057100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$31CFE05C-C9D7-4951-8E0C-6651078730D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"675a87b12bc3cf5bbe8f6eb11cc8f57912f55986","datavalue":{"value":"measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$D378BFB7-C9CE-4CA3-B6D2-C88BE0B1DE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24b6d2042d21e76f77d23786856aab9044859a84","datavalue":{"value":"vulnerability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$8567E215-ED00-4C59-A08D-B5A6C0B171BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17722f49fcd88b1244cfbd7b4d85bd30cb78b38e","datavalue":{"value":"binding number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$21267C13-6E33-4FE5-84E7-90681A1F6BC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d85b939a4a0ff86505891a908b4d1c8201d4540b","datavalue":{"value":"thoughness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$991D668B-F1ED-45E3-B023-95F1E472A35C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9a04a453e91c79c7e831d838f6c5e3a9e0859a2","datavalue":{"value":"scattering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$1D6ED57D-FC97-4DB5-90D0-E4A630A61E78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09ca41b248cd35e115d1e984d56db3a0f9aaed2f","datavalue":{"value":"vertex integrity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$1EA0F52C-F59E-49BA-9122-604B9BABFDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fab59217e5005edd2080f549b4c2a3c78cc325c6","datavalue":{"value":"minimum balanced separator problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$8A50344D-1AFB-4576-9279-C1028DD98391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d85c121e6e6200a1d4667137fca957de2656737","datavalue":{"value":"polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$932891A1-FA40-4A53-9879-A1A7DC8146CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b263e36ca18258b426217c2ef6f3d9276b20c1b3","datavalue":{"value":"trapezoid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$8EF00645-F2C9-4F8F-92B1-6C35C8A60628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364473$67322296-3A41-4ED9-98A0-35A75E679D2A","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":"Q1364473$856D66A7-4F7C-4823-993E-36E09226C2D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d88001a2f34e2beb6ce71bcd3f8f8ac4106f98fe","datavalue":{"value":{"entity-type":"item","numeric-id":3789603,"id":"Q3789603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$903FE5E0-8C5D-41B2-A05C-890752AE9944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"261b30465b2f9b97ed6391eb2fa761c1d658a808","datavalue":{"value":{"entity-type":"item","numeric-id":918697,"id":"Q918697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$82679E86-F4F0-495F-9860-9C52C3D8B547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f969d00bcd038d3680c3e73bfbbbe2df0b64d924","datavalue":{"value":{"entity-type":"item","numeric-id":4863978,"id":"Q4863978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$3BC49102-3605-4404-B625-3EFACA3C5E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$AFDE51D5-538B-4BC0-A143-C19CFD8265D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3ef294054fdcfb1a9e7a1dfde5ad70e8ba52c2","datavalue":{"value":{"entity-type":"item","numeric-id":3775581,"id":"Q3775581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$821C18BA-5F5A-4B68-8931-4CB5C4C91AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79cc333a398e9d6212f316ca27b812994cbe7ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1111577,"id":"Q1111577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$942749AF-90C2-4376-80BF-462C3AC18130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5412029a0de44f9f3f2a7784aa6f0e11fb01c84","datavalue":{"value":{"entity-type":"item","numeric-id":678864,"id":"Q678864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$572B73D1-4CA2-4C9F-85EB-1259A8EF3CAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31403449edcb685befef57967c6d318e33df55c0","datavalue":{"value":{"entity-type":"item","numeric-id":1247984,"id":"Q1247984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$D95ECBB8-867F-4DA4-8572-51C6C0BA5A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$5D3B4959-B029-4A4B-8FAE-5BE27A44122F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fedf0dbbb6ce3fde8c109c205962b57beb6a4525","datavalue":{"value":{"entity-type":"item","numeric-id":3138973,"id":"Q3138973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$F2DC54D3-5123-4E15-8DE5-CCE3CD555C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd8d7183a116f2f09d1dc606ebc6b096875ef53","datavalue":{"value":{"entity-type":"item","numeric-id":3691700,"id":"Q3691700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$4C730D15-5F80-460B-B5C7-3273326E9267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"891f642347d0eff21783dfafe83d88929d7ccfe0","datavalue":{"value":{"entity-type":"item","numeric-id":1824634,"id":"Q1824634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$4751B08C-7099-4AC9-BCD5-35899E8FBC0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"986b73a9353ad02bc4272d4b7390d18157c37227","datavalue":{"value":{"entity-type":"item","numeric-id":5966492,"id":"Q5966492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$BDD116BD-2D68-46E3-8511-0C4B5018C949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0af54e1c50e8248a0478c03b44c05aa07b1048","datavalue":{"value":{"entity-type":"item","numeric-id":5666592,"id":"Q5666592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364473$AEFFC447-56DD-428A-BF57-68158CDB1D73","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c02f7005c4bcc3bc6e5487a433068023a3df4f96","datavalue":{"value":"W2012676186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364473$D0AC4716-745C-4573-A492-4DC84F0FEE2C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce0029e08987e03b5edd60a452cbb72be223d689","datavalue":{"value":{"entity-type":"item","numeric-id":5016061,"id":"Q5016061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f8e37766e8e403a0584d4642642456889173c16","datavalue":{"value":{"amount":"+0.8273357152938843","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364473$BBF46717-AC3E-4DAE-BE3B-E8C20454D16F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90ccf758a8d6d786bd847eb571a3deafee9a9fa4","datavalue":{"value":{"entity-type":"item","numeric-id":4264550,"id":"Q4264550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70e3480f4befd366140495654bcf003fb2704419","datavalue":{"value":{"amount":"+0.7949978709220886","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364473$B2A35C0B-9741-46A8-9E27-4B7C25FCD99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d6b449aeedaf7cd5aa782d73fa832485d72b478","datavalue":{"value":{"entity-type":"item","numeric-id":5438691,"id":"Q5438691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df68892807cb3ac765ebb04734a8ad7fce1ec4bc","datavalue":{"value":{"amount":"+0.7828831076622009","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364473$A958AE9C-CB16-4B74-ACF0-E28618726BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"075f6b16772f7e4890b58b86c5fdcf052104f295","datavalue":{"value":{"entity-type":"item","numeric-id":4303624,"id":"Q4303624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d589fb844f52a4e6ec7b7e11d08c9da8b2dd53c8","datavalue":{"value":{"amount":"+0.7809295654296875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1364473$7DEBD0FE-5800-4E76-837A-7F3AF28B9BC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1364473","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1364473"}}}}}