✦ LIBER ✦

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

✍ Scribed by Hiroshi Nagamochi; Toshihide Ibaraki

Publisher: Springer
Year: 1992
Tongue: English
Weight: 684 KB
Volume: 7
Category: Article
ISSN: 0178-4617
DOI: 10.1007/bf01758778

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A 2-Approximation Algorithm for Finding

A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

✍ Vincenzo Auletta; Yefim Dinitz; Zeev Nutov; Domenico Parente 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 71 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs Ž and of k-out-connected graphs i.e., graphs which contain a vertex

A linear time 53-approximation for the m

A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem

✍ Liang Zhao; Hiroshi Nagamochi; Toshihide Ibaraki 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 134 KB

A linear time 5 3 -approximation algorithm is presented for the NP-hard problem of finding a minimum strongly-connected spanning subgraph. It is based on cycle contraction that was first introduced by Khuller, Raghavachari and Young [SIAM J. Comput. 24 (1995) 859-872]. We improve their result by con

A 3-Approximation Algorithm for Finding

A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

✍ Yefim Dinitz; Zeev Nutov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 103 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, Ä 4 we derive a 3-approximation algorithm for k g 4, 5 . This

An algorithm for finding a minimal equiv

An algorithm for finding a minimal equivalent graph of a strongly connected digraph

✍ S. Martello 📂 Article 📅 1979 🏛 Springer Vienna 🌐 English ⚖ 505 KB

A linear-time algorithm for four-partiti

A linear-time algorithm for four-partitioning four-connected planar graphs

✍ Shin-ichi Nakano; Md.Saidur Rahman; Takao Nishizeki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 765 KB

In this paper we give a simple linear-time algorithm to find such a partition if G is a 4-connected planar graph and ~1. ~2. 143 and u4 are located on the same face of a plane embedding of G. Our algorithm is based on a "4canonical decomposition" of G, which is a generalization of an St-numbering an

A linear time algorithm for finding dept

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs

✍ Hon-Chan Chen; Yue-Li Wang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 458 KB

Let G be a connected graph of n vertices and m edges. The problem of finding a depth-first spanning tree of G is to find a subgraph of G connecting the n vertices with n -1 edges by depth-first search. In this paper, we propose an O(n) time algorithm for solving this problem on trapezoid graphs. Our