Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity

The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as constructing a graph that is a union of these paths. This construction relies on the computation of biconnected components and bridges of the source graph. A new al...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer & systems sciences international 2021-03, Vol.60 (2), p.213-226
Main Author: Golovinskii, I. A.
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Computation
Control
Engineering
Graph theory
Graphs
Mechatronics
Robotics
Systems Analysis and Operations Research
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c268t-f504da8f67f3ca5a519cee36c15c299b9a262dc16ea979736ec37ec1bed8c8953
container_end_page 226
container_issue 2
container_start_page 213
container_title Journal of computer & systems sciences international
container_volume 60
creator Golovinskii, I. A.
description The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as constructing a graph that is a union of these paths. This construction relies on the computation of biconnected components and bridges of the source graph. A new algorithm which makes this computation more transparent and controllable is proposed. Its idea is to track opening and closing of chords at the depth-first search. Due to the clarity of the proposed solution, its correctness is obvious without much justification. This is its advantage over the well-known Hopcroft–Tarjan algorithm. The proposed algorithm makes self-evident the obtaining biconnected components of a graph by successive uniting its fundamental cycles that have common edges.
doi_str_mv 10.1134/S1064230721020040
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2519366497</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2519366497</sourcerecordid><originalsourceid>FETCH-LOGICAL-c268t-f504da8f67f3ca5a519cee36c15c299b9a262dc16ea979736ec37ec1bed8c8953</originalsourceid><addsrcrecordid>eNp1kM1KAzEURoMoWKsP4C7gemp-JpmJu1q0FooKreshTTM2tU3GJKN052v4ej6JKSO4EFf3wv3O4fIBcI7RAGOaX84w4jmhqCAYEYRydAB6mDGWcUbRYdrTOdvfj8FJCGuEqOAo74HFyNkQfauicRa6Gs7Mttlo-CjjCo69bFYBGgvnXtrQOB_hvY7vzr-EKziZDODQys0umLAnu_TXxye8NspZq5PzzcTdKTiq5Sbos5_ZB0-3N_PRXTZ9GE9Gw2mmCC9jVjOUL2VZ86KmSjLJsFBaU64wU0SIhZCEk6XCXEtRiIJyrWihFV7oZalKwWgfXHTexrvXVodYrV3r04OhIklGOc8T1ge4SynvQvC6rhpvttLvKoyqfZXVnyoTQzompKx91v7X_D_0DelXdoU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2519366497</pqid></control><display><type>article</type><title>Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity</title><source>Springer Link</source><creator>Golovinskii, I. A.</creator><creatorcontrib>Golovinskii, I. A.</creatorcontrib><description>The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as constructing a graph that is a union of these paths. This construction relies on the computation of biconnected components and bridges of the source graph. A new algorithm which makes this computation more transparent and controllable is proposed. Its idea is to track opening and closing of chords at the depth-first search. Due to the clarity of the proposed solution, its correctness is obvious without much justification. This is its advantage over the well-known Hopcroft–Tarjan algorithm. The proposed algorithm makes self-evident the obtaining biconnected components of a graph by successive uniting its fundamental cycles that have common edges.</description><identifier>ISSN: 1064-2307</identifier><identifier>EISSN: 1555-6530</identifier><identifier>DOI: 10.1134/S1064230721020040</identifier><language>eng</language><publisher>Moscow: Pleiades Publishing</publisher><subject>Algorithms ; Apexes ; Computation ; Control ; Engineering ; Graph theory ; Graphs ; Mechatronics ; Robotics ; Systems Analysis and Operations Research</subject><ispartof>Journal of computer &amp; systems sciences international, 2021-03, Vol.60 (2), p.213-226</ispartof><rights>Pleiades Publishing, Ltd. 2021. ISSN 1064-2307, Journal of Computer and Systems Sciences International, 2021, Vol. 60, No. 2, pp. 213–226. © Pleiades Publishing, Ltd., 2021. Russian Text © The Author(s), 2021, published in Izvestiya Akademii Nauk, Teoriya i Sistemy Upravleniya, 2021, No. 2, pp. 47–61.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c268t-f504da8f67f3ca5a519cee36c15c299b9a262dc16ea979736ec37ec1bed8c8953</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Golovinskii, I. A.</creatorcontrib><title>Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity</title><title>Journal of computer &amp; systems sciences international</title><addtitle>J. Comput. Syst. Sci. Int</addtitle><description>The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as constructing a graph that is a union of these paths. This construction relies on the computation of biconnected components and bridges of the source graph. A new algorithm which makes this computation more transparent and controllable is proposed. Its idea is to track opening and closing of chords at the depth-first search. Due to the clarity of the proposed solution, its correctness is obvious without much justification. This is its advantage over the well-known Hopcroft–Tarjan algorithm. The proposed algorithm makes self-evident the obtaining biconnected components of a graph by successive uniting its fundamental cycles that have common edges.</description><subject>Algorithms</subject><subject>Apexes</subject><subject>Computation</subject><subject>Control</subject><subject>Engineering</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mechatronics</subject><subject>Robotics</subject><subject>Systems Analysis and Operations Research</subject><issn>1064-2307</issn><issn>1555-6530</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp1kM1KAzEURoMoWKsP4C7gemp-JpmJu1q0FooKreshTTM2tU3GJKN052v4ej6JKSO4EFf3wv3O4fIBcI7RAGOaX84w4jmhqCAYEYRydAB6mDGWcUbRYdrTOdvfj8FJCGuEqOAo74HFyNkQfauicRa6Gs7Mttlo-CjjCo69bFYBGgvnXtrQOB_hvY7vzr-EKziZDODQys0umLAnu_TXxye8NspZq5PzzcTdKTiq5Sbos5_ZB0-3N_PRXTZ9GE9Gw2mmCC9jVjOUL2VZ86KmSjLJsFBaU64wU0SIhZCEk6XCXEtRiIJyrWihFV7oZalKwWgfXHTexrvXVodYrV3r04OhIklGOc8T1ge4SynvQvC6rhpvttLvKoyqfZXVnyoTQzompKx91v7X_D_0DelXdoU</recordid><startdate>20210301</startdate><enddate>20210301</enddate><creator>Golovinskii, I. A.</creator><general>Pleiades Publishing</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20210301</creationdate><title>Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity</title><author>Golovinskii, I. A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c268t-f504da8f67f3ca5a519cee36c15c299b9a262dc16ea979736ec37ec1bed8c8953</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithms</topic><topic>Apexes</topic><topic>Computation</topic><topic>Control</topic><topic>Engineering</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mechatronics</topic><topic>Robotics</topic><topic>Systems Analysis and Operations Research</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Golovinskii, I. A.</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Journal of computer &amp; systems sciences international</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Golovinskii, I. A.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity</atitle><jtitle>Journal of computer &amp; systems sciences international</jtitle><stitle>J. Comput. Syst. Sci. Int</stitle><date>2021-03-01</date><risdate>2021</risdate><volume>60</volume><issue>2</issue><spage>213</spage><epage>226</epage><pages>213-226</pages><issn>1064-2307</issn><eissn>1555-6530</eissn><abstract>The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as constructing a graph that is a union of these paths. This construction relies on the computation of biconnected components and bridges of the source graph. A new algorithm which makes this computation more transparent and controllable is proposed. Its idea is to track opening and closing of chords at the depth-first search. Due to the clarity of the proposed solution, its correctness is obvious without much justification. This is its advantage over the well-known Hopcroft–Tarjan algorithm. The proposed algorithm makes self-evident the obtaining biconnected components of a graph by successive uniting its fundamental cycles that have common edges.</abstract><cop>Moscow</cop><pub>Pleiades Publishing</pub><doi>10.1134/S1064230721020040</doi><tpages>14</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1064-2307
ispartof Journal of computer & systems sciences international, 2021-03, Vol.60 (2), p.213-226
issn 1064-2307
1555-6530
language eng
recordid cdi_proquest_journals_2519366497
source Springer Link
subjects Algorithms
Apexes
Computation
Control
Engineering
Graph theory
Graphs
Mechatronics
Robotics
Systems Analysis and Operations Research
title Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-07T15%3A47%3A45IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Construction%20of%20Simple%20Path%20Graphs%20in%20Transport%20Networks:%20II.%20Analysis%20of%20Graphs%E2%80%99%20Biconnectivity&rft.jtitle=Journal%20of%20computer%20&%20systems%20sciences%20international&rft.au=Golovinskii,%20I.%20A.&rft.date=2021-03-01&rft.volume=60&rft.issue=2&rft.spage=213&rft.epage=226&rft.pages=213-226&rft.issn=1064-2307&rft.eissn=1555-6530&rft_id=info:doi/10.1134/S1064230721020040&rft_dat=%3Cproquest_cross%3E2519366497%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c268t-f504da8f67f3ca5a519cee36c15c299b9a262dc16ea979736ec37ec1bed8c8953%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2519366497&rft_id=info:pmid/&rfr_iscdi=true