{"updated":"2025-01-22T16:09:19.451814+00:00","links":{},"id":32469,"created":"2025-01-18T23:01:33.054679+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00032469","sets":["1164:2592:2693:2697"]},"path":["2697"],"owner":"1","recid":"32469","title":["グラフの多重辺付加を許さない4辺連結化問題"],"pubdate":{"attribute_name":"公開日","attribute_value":"1993-05-28"},"_buckets":{"deposit":"ab208458-c769-489b-a722-7127d6647dbb"},"_deposit":{"id":"32469","pid":{"type":"depid","value":"32469","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"グラフの多重辺付加を許さない4辺連結化問題","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"グラフの多重辺付加を許さない4辺連結化問題"},{"subitem_title":"Simplicity - Preserving Augmentation to 4 -Edge- Connect a Graph","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1993-05-28","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"広島大学工学部第二類回路システム工学講座"},{"subitem_text_value":"広島大学工学部第二類回路システム工学講座"},{"subitem_text_value":"広島大学工学部第二類回路システム工学講座"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Circuits and Systems, Faculty of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Department of Circuits and Systems, Faculty of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Department of Circuits and Systems, Faculty of Engineering, Hiroshima University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/32469/files/IPSJ-AL93033005.pdf"},"date":[{"dateType":"Available","dateValue":"1995-05-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL93033005.pdf","filesize":[{"value":"1.4 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"dbb3f03e-cb41-4240-a59a-5965bc25dd13","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1993 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"高藤, 大介"},{"creatorName":"田岡, 智志"},{"creatorName":"渡辺, 敏正"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Daisuke, Takafuji","creatorNameLang":"en"},{"creatorName":"Satoshi, Taoka","creatorNameLang":"en"},{"creatorName":"Toshimasa, Watanabe","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"重みなしのk辺連結化問題（(?4ECAと略記）とは，与えられた無向グラフG=（，）に付加すれば得られるグラフG'=（，A∪A'）がk辺連結となるような最小辺集合A'を求める問題である．G，G'共に単純グラフとしたUW?4ECAをUW?4ECA（，)と表し，Gは多重グラフでもよいがG'構成時の多重辺付加は許さない場合をUW?4ECA（^*，)と表す．本稿ではUW?4ECA（，)に対するO（｜N｜^）アルゴリズムを提案する．これはUW?4ECA（^*，)にも応用できる．また，葉グラフと呼ばれるグラフの最大マッチングの辺数も示している．本結果は未解決問題である一般的なUW?kECA（^*，)の解決に向けての第一歩である．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"The unweighted k-edge-connectivity augmentation problem (UW-kECA) is defined by \"Given a graph G=(N,A), find an edge set A' of minimum cardinality, with each element connecting distinct vertices of N, such that G'=N,A∪A') is k-edge-connected.\" Let UW-4ECA(S,SA) denote UW-kECA such that both G and G' are simple. The paper proposes an O(｜N｜^2) algorithm for solving UW-4ECA(S,SA). The result can be used in solving UW-4ECA(^*,SA) in which G may have multiple edges and creation of new multiple edges in constructing G' is not allowed. Also presented is the cardinality of a maximum matching of a leaf graph that is constructed from G, and the results may be interesting from viewpoint of combinatorial theory. The paper is a first step toward an open problem UW-kECA(^*,SA) for general k〓4.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"40","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"33","bibliographicIssueDates":{"bibliographicIssueDate":"1993-05-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"48(1993-AL-033)","bibliographicVolumeNumber":"1993"}]},"relation_version_is_last":true,"weko_creator_id":"1"}}