DOI: 10.1016/0196-6774(87)90042-3. Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs

Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs

10.1016/0196-6774(87)90042-3

Crossref journal-article

Elsevier BV

Journal of Algorithms (78)

Bibliography

Lengauer, T. (1987). Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs. Journal of Algorithms, 8(2), 260â284.

Authors 1

T Lengauer (first)

References 13 Referenced 25

H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorika, in press. (10.1007/BF02579168)
{'key': '10.1016/0196-6774(87)90042-3_BIB2', 'series-title': 'Computers and Intractibility: A Guide to the Theory of NP-Completeness', 'author': 'Garey', 'year': '1979'} / Computers and Intractibility: A Guide to the Theory of NP-Completeness by Garey (1979)
{'key': '10.1016/0196-6774(87)90042-3_BIB3', 'series-title': 'Proceedings, Conference on Advanced Research in VLSI', 'first-page': '139', 'article-title': 'The HILL-System: A design environment for the hierarchical specification, compaction, and simulation of integrated circuit layouts', 'author': 'Lengauer', 'year': '1984'} / Proceedings, Conference on Advanced Research in VLSI / The HILL-System: A design environment for the hierarchical specification, compaction, and simulation of integrated circuit layouts by Lengauer (1984)
{'key': '10.1016/0196-6774(87)90042-3_BIB4', 'series-title': 'SICOMP 13.2', 'first-page': '338', 'article-title': 'Fast algorithms for findings nearest common ancestors', 'author': 'Harel', 'year': '1984'} / SICOMP 13.2 / Fast algorithms for findings nearest common ancestors by Harel (1984)
{'key': '10.1016/0196-6774(87)90042-3_BIB5', 'series-title': 'Proceedings, 23rd IEEE-FOCS', 'first-page': '358', 'article-title': 'The complexity of compacting hierarchically specified layouts of integrated circuits', 'author': 'Lengauer', 'year': '1982'} / Proceedings, 23rd IEEE-FOCS / The complexity of compacting hierarchically specified layouts of integrated circuits by Lengauer (1982)
{'key': '10.1016/0196-6774(87)90042-3_BIB6_1', 'article-title': 'Efficient solution of connectivity problems on hierarchically defined graphs', 'author': 'Lengauer', 'year': '1985'} / Efficient solution of connectivity problems on hierarchically defined graphs by Lengauer (1985)
{'key': '10.1016/0196-6774(87)90042-3_BIB6_2', 'series-title': "Proceedings of the WG '85", 'year': '1985'} / Proceedings of the WG '85 (1985)
10.1007/3-540-16761-7_71 / Proc. of 13th ICALP Springer Lecture Notes on Computer Science No. 226 / Hierarchical planarity testing algorithms by Lengauer (1986)
{'key': '10.1016/0196-6774(87)90042-3_BIB8', 'series-title': 'Proc. of AWOC 86', 'first-page': '180', 'article-title': 'Exploiting Hierarchy in VLSI Design', 'author': 'Lengauer', 'year': '1986'} / Proc. of AWOC 86 / Exploiting Hierarchy in VLSI Design by Lengauer (1986)
{'key': '10.1016/0196-6774(87)90042-3_BIB9', 'series-title': 'Proc. of STACS 87', 'article-title': 'The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems', 'author': 'Lengauer', 'year': '1987'} / Proc. of STACS 87 / The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems by Lengauer (1987)
{'key': '10.1016/0196-6774(87)90042-3_BIB10', 'series-title': 'Data structures and Network Algorithms', 'author': 'Tarjan', 'year': '1983'} / Data structures and Network Algorithms by Tarjan (1983)
{'key': '10.1016/0196-6774(87)90042-3_BIB11_1', 'article-title': 'Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles', 'author': 'Widmayer', 'year': '1985'} / Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles by Widmayer (1985)
{'key': '10.1016/0196-6774(87)90042-3_BIB11_2', 'article-title': "Proceedings, WG '85", 'author': 'Widmayer', 'year': '1985'} / Proceedings, WG '85 by Widmayer (1985)

Dates

Type	When
Created	20 years, 10 months ago (Nov. 6, 2004, 8:03 a.m.)
Deposited	6 years, 7 months ago (Feb. 1, 2019, 10:57 p.m.)
Indexed	2 years, 8 months ago (Jan. 2, 2023, 5:17 p.m.)
Issued	38 years, 3 months ago (June 1, 1987)
Published	38 years, 3 months ago (June 1, 1987)
Published Print	38 years, 3 months ago (June 1, 1987)

Funders 0

None

BibTeX

@article{Lengauer_1987, title={Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs}, volume={8}, ISSN={0196-6774}, url={http://dx.doi.org/10.1016/0196-6774(87)90042-3}, DOI={10.1016/0196-6774(87)90042-3}, number={2}, journal={Journal of Algorithms}, publisher={Elsevier BV}, author={Lengauer, T}, year={1987}, month=jun, pages={260–284} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2023,
        1,
        2
      ]
    ],
    "date-time": "2023-01-02T22:17:33Z",
    "timestamp": 1672697853455
  },
  "reference-count": 13,
  "publisher": "Elsevier BV",
  "issue": "2",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1987,
            6,
            1
          ]
        ],
        "date-time": "1987-06-01T00:00:00Z",
        "timestamp": 549504000000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "https://www.elsevier.com/tdm/userlicense/1.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1987,
        6
      ]
    ]
  },
  "DOI": "10.1016/0196-6774(87)90042-3",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2004,
        11,
        6
      ]
    ],
    "date-time": "2004-11-06T13:03:10Z",
    "timestamp": 1099746190000
  },
  "page": "260-284",
  "source": "Crossref",
  "is-referenced-by-count": 25,
  "title": "Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs",
  "prefix": "10.1016",
  "volume": "8",
  "author": [
    {
      "given": "T",
      "family": "Lengauer",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "78",
  "reference": [
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB1",
      "doi-asserted-by": "crossref",
      "unstructured": "H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorika, in press.",
      "DOI": "10.1007/BF02579168"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB2",
      "series-title": "Computers and Intractibility: A Guide to the Theory of NP-Completeness",
      "author": "Garey",
      "year": "1979"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB3",
      "series-title": "Proceedings, Conference on Advanced Research in VLSI",
      "first-page": "139",
      "article-title": "The HILL-System: A design environment for the hierarchical specification, compaction, and simulation of integrated circuit layouts",
      "author": "Lengauer",
      "year": "1984"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB4",
      "series-title": "SICOMP 13.2",
      "first-page": "338",
      "article-title": "Fast algorithms for findings nearest common ancestors",
      "author": "Harel",
      "year": "1984"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB5",
      "series-title": "Proceedings, 23rd IEEE-FOCS",
      "first-page": "358",
      "article-title": "The complexity of compacting hierarchically specified layouts of integrated circuits",
      "author": "Lengauer",
      "year": "1982"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB6_1",
      "article-title": "Efficient solution of connectivity problems on hierarchically defined graphs",
      "author": "Lengauer",
      "year": "1985"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB6_2",
      "series-title": "Proceedings of the WG '85",
      "year": "1985"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB7",
      "series-title": "Proc. of 13th ICALP Springer Lecture Notes on Computer Science No. 226",
      "doi-asserted-by": "crossref",
      "first-page": "215",
      "DOI": "10.1007/3-540-16761-7_71",
      "article-title": "Hierarchical planarity testing algorithms",
      "author": "Lengauer",
      "year": "1986"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB8",
      "series-title": "Proc. of AWOC 86",
      "first-page": "180",
      "article-title": "Exploiting Hierarchy in VLSI Design",
      "author": "Lengauer",
      "year": "1986"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB9",
      "series-title": "Proc. of STACS 87",
      "article-title": "The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems",
      "author": "Lengauer",
      "year": "1987"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB10",
      "series-title": "Data structures and Network Algorithms",
      "author": "Tarjan",
      "year": "1983"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB11_1",
      "article-title": "Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles",
      "author": "Widmayer",
      "year": "1985"
    },
    {
      "key": "10.1016/0196-6774(87)90042-3_BIB11_2",
      "article-title": "Proceedings, WG '85",
      "author": "Widmayer",
      "year": "1985"
    }
  ],
  "container-title": "Journal of Algorithms",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.elsevier.com/content/article/PII:0196677487900423?httpAccept=text/xml",
      "content-type": "text/xml",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://api.elsevier.com/content/article/PII:0196677487900423?httpAccept=text/plain",
      "content-type": "text/plain",
      "content-version": "vor",
      "intended-application": "text-mining"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        2,
        2
      ]
    ],
    "date-time": "2019-02-02T03:57:12Z",
    "timestamp": 1549079832000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://linkinghub.elsevier.com/retrieve/pii/0196677487900423"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1987,
        6
      ]
    ]
  },
  "references-count": 13,
  "journal-issue": {
    "issue": "2",
    "published-print": {
      "date-parts": [
        [
          1987,
          6
        ]
      ]
    }
  },
  "alternative-id": [
    "0196677487900423"
  ],
  "URL": "http://dx.doi.org/10.1016/0196-6774(87)90042-3",
  "relation": {},
  "ISSN": [
    "0196-6774"
  ],
  "subject": [],
  "container-title-short": "Journal of Algorithms",
  "published": {
    "date-parts": [
      [
        1987,
        6
      ]
    ]
  }
}