Minmax Strongly Connected Subgraphs with Node Penalties

Punnen, Abraham

doi:10.1155/JAMDS.2005.107

Resource type

Article

Date created

2005

Authors/Contributors

Author: Punnen, Abraham

Abstract

We propose an O(min{m+nlogn,mlog∗n}) to find a minmax strongly connected spanningsubgraph of a digraph with n nodes and m arcs. A generalization of this problemcalled theminmax strongly connected subgraph problem with node penalties is also considered.An O(mlogn) algorithm is proposed to solve this general problem. We also discussways to improve the average complexity of this algorithm.

Published as

Journal of Applied Mathematics and Decision Sciences
Volume 2005 (2005), Issue 2, Pages 107-111
http://dx.doi.org/10.1155/JAMDS.2005.107

Publication details

Publication title

Journal of Applied Mathematics and Decision Sciences

Document title

Minmax Strongly Connected Subgraphs with Node Penalties

Date

2005

Volume

2005

Issue

2

First page

107

Last page

111

Publisher DOI

10.1155/JAMDS.2005.107

Copyright statement

Copyright is held by the author(s).

Permissions

You are free to copy, distribute and transmit this work under the following conditions: You must give attribution to the work (but not in any way that suggests that the author endorses you or your use of the work); You may not use this work for commercial purposes.

Scholarly level

Faculty/Staff

Peer reviewed?

Yes

Language

English

Member of collection

Mathematics

Download file	Size
684573.pdf	2.27 MB

Minmax Strongly Connected Subgraphs with Node Penalties

Views & downloads - as of June 2023