{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T07:09:51Z","timestamp":1648969791087},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,4]]},"abstract":"<jats:p> We present algorithms that construct a sparse spanning subgraph of a three-edge-connected graph that preserves three-edge connectivity or of a three-vertex-connected graph that preserves three-vertex connectivity. Our algorithms are conceptually simple and run in O(|E|) time. These simple algorithms can be used to improve the efficiency of the best-known algorithms for three-edge and three-vertex connectivity and their related problems, by preprocessing the input graph so as to trim it down to a sparse graph. Afterwards, the original algorithms run in O(|V|) instead of O(|E|) time. Our algorithms generate an adjacency-lists structure to represent the sparse spanning subgraph, so that when a depth-first search is performed over the subgraph based on this adjacency-lists structure it actually traverses the paths in an ear-decomposition of the subgraph. This is useful because many of the existing algorithms for three-edge- or three-vertex connectivity and their related problems are based on an ear-decomposition of the given graph. Using such an adjacency-lists structure to represent the input graph would greatly improve the run-time efficiency of these algorithms. <\/jats:p>","DOI":"10.1142\/s012905411450018x","type":"journal-article","created":{"date-parts":[[2014,7,25]],"date-time":"2014-07-25T05:48:52Z","timestamp":1406267332000},"page":"355-368","source":"Crossref","is-referenced-by-count":0,"title":["ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS"],"prefix":"10.1142","volume":"25","author":[{"given":"AMR","family":"ELMASRY","sequence":"first","affiliation":[{"name":"Department of Computer Engineering and Systems, Alexandria University, Alexandria, Egypt"}]},{"given":"YUNG H.","family":"TSIN","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Windsor, Windsor, Ontario, Canada"}]}],"member":"219","published-online":{"date-parts":[[2014,7,24]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9665-z"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129183106009989"},{"key":"p_4","first-page":"13","volume":"4169","author":"Dehne F.","year":"2006","journal-title":"LNCS"},{"key":"p_6","first-page":"375","volume":"6507","author":"Elmasry A.","year":"2010","journal-title":"LNCS"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1145\/122413.122416"},{"key":"p_9","first-page":"77","volume":"1984","author":"Gutwenger C.","year":"2000","journal-title":"LNCS"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2012.09.007"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167564"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"p_18","first-page":"410","volume":"6044","author":"Paten B.","year":"2010","journal-title":"LNCS"},{"issue":"3","key":"p_21","first-page":"410","volume":"75","author":"Taoka S.","year":"1992","journal-title":"IEICE Transactions Fundamentals"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1269-4"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.003"},{"key":"p_25","first-page":"3","author":"Tsin Y. H.","year":"2012","journal-title":"Australia"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411450018X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:54:37Z","timestamp":1565200477000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411450018X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":17,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2014,7,24]]},"published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1142\/S012905411450018X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411450018x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]}}}