{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T15:18:52Z","timestamp":1746803932842,"version":"3.40.5"},"reference-count":19,"publisher":"Elsevier BV","issue":"7","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2014,4,6]],"date-time":"2014-04-06T00:00:00Z","timestamp":1396742400000},"content-version":"vor","delay-in-days":1466,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1016\/j.dam.2009.10.008","type":"journal-article","created":{"date-parts":[[2010,2,17]],"date-time":"2010-02-17T09:17:06Z","timestamp":1266398226000},"page":"779-799","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"title":["<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" altimg=\"si8.gif\" display=\"inline\" overflow=\"scroll\"><mml:mi>O<\/mml:mi><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>m<\/mml:mi><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math> split decomposition of strongly-connected graphs"],"prefix":"10.1016","volume":"158","author":[{"given":"Benson L.","family":"Joeris","sequence":"first","affiliation":[]},{"given":"Scott","family":"Lundberg","sequence":"additional","affiliation":[]},{"given":"Ross M.","family":"McConnell","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2009.10.008_b1","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","article-title":"Distance-hereditary graphs","volume":"41","author":"Bandelt","year":"1986","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"10.1016\/j.dam.2009.10.008_b2","doi-asserted-by":"crossref","DOI":"10.1137\/0608028","article-title":"Digraph decompositions and eulerian systems","volume":"8","author":"Bouchet","year":"1987","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"10.1016\/j.dam.2009.10.008_b3","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02579301","article-title":"Reducing prime graphs and recognizing circle graphs","volume":"7","author":"Bouchet","year":"1987","journal-title":"Combinatorica"},{"key":"10.1016\/j.dam.2009.10.008_b4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0166-218X(99)00074-8","article-title":"On the extension of bipartite to parity graphs","volume":"95","author":"Cicerone","year":"1999","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0012-365X(85)80001-7","article-title":"Compositions for perfect graphs","volume":"55","author":"Cornuejols","year":"1985","journal-title":"Discrete Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b6","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","article-title":"Decomposition of directed graphs","volume":"3","author":"Cunningham","year":"1982","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"10.1016\/j.dam.2009.10.008_b7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1090","article-title":"Parallel algorithms for hierarchical clustering, and applications to split decomposition and parity graph recognition","volume":"36","author":"Dahlhaus","year":"2000","journal-title":"Journal of Algorithms"},{"key":"10.1016\/j.dam.2009.10.008_b8","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/65950.65951","article-title":"Recognizing circle graphs in polynomial time","volume":"36","author":"Gabor","year":"1989","journal-title":"Journal of the ACM"},{"key":"10.1016\/j.dam.2009.10.008_b9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","article-title":"Completely separable graphs","volume":"27","author":"Hammer","year":"1990","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(02)00435-8","article-title":"PC trees and circular-ones arrangements","volume":"296","author":"Hsu","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.dam.2009.10.008_b11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jagm.1994.1007","article-title":"An O(n2) algorithm for undirected split decomposition","volume":"16","author":"Ma","year":"1994","journal-title":"Journal of Algorithms"},{"key":"10.1016\/j.dam.2009.10.008_b12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02022041","article-title":"Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions","volume":"4","author":"M\u00f6hring","year":"1985","journal-title":"Annals of Operations Research"},{"key":"10.1016\/j.dam.2009.10.008_b13","first-page":"257","article-title":"Substitution decomposition for discrete structures and connections with combinatorial optimization","volume":"19","author":"M\u00f6hring","year":"1984","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b14","article-title":"Solving some NP-complete problems using split decomposition","author":"Rao","year":"2007","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b15","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/0402051","article-title":"Prime testing for the split decomposition of a graph","volume":"2","author":"Spinrad","year":"1989","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"10.1016\/j.dam.2009.10.008_b16","unstructured":"J.P. Spinrad, Two Dimensional Partial Orders, Ph.D. thesis, Princeton University, 1982"},{"key":"10.1016\/j.dam.2009.10.008_b17","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","article-title":"On comparability and permutation graphs","volume":"14","author":"Spinrad","year":"1985","journal-title":"Siam Journal on Computing"},{"key":"10.1016\/j.dam.2009.10.008_b18","unstructured":"J.P. Spinrad, Graph partitioning, unpublished manuscript, 1985"},{"key":"10.1016\/j.dam.2009.10.008_b19","series-title":"Proceedings of the 10th Colloquium on Automata, Languages, and Programming","first-page":"676","article-title":"Recognition and isomorphism of two-dimensional partial orders","author":"Spinrad","year":"1983"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X09003953?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X09003953?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T00:37:08Z","timestamp":1660264628000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X09003953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":19,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["S0166218X09003953"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2009.10.008","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"split decomposition of strongly-connected graphs","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2009.10.008","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2009 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}