A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

descriptionPublicationkeyboard_double_arrow_right Article 01 Jun 1992 English Publisher:Springer Science and Business Media LLCJournal:Algorithmica, volume 7, pages 583-596 (issn: 0178-4617, eissn: 1432-0541,

Copyright policy )

Authors: Hiroshi Nagamochi; Toshihide Ibaraki;

doi: 10.1007/bf01758778

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

- Summary
- Subjects
- Metrics

Abstract

The authors present a linear-time algorithm for finding a sparse \(k\)- connected spanning subgraph for a given \(k\)-connected undirected graph. This is used to improve the time complexities of other graph connectivity problems.

Related Organizations

Kyoto University
Japan

Keywords

Connectivity, linear-time algorithm, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, time complexities, graph connectivity problems, \(k\)-connected spanning subgraph

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	218
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 1%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 0.1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%