NDLI: Two Variations of the Minimum Steiner Problem

Content Provider	Springer Nature Link
Author	Hsu, Tsan Sheng Tsai, Kuo Hui Wang, Da Wei Lee, D. T.
Copyright Year	2005
Abstract	Given a set S of starting vertices and a set T of terminating vertices in a graph G = (V,E) with non-negative weights on edges, the minimum Steiner network problem is to find a subgraph of G with the minimum total edge weight. In such a subgraph, we require that for each vertex s $${\in}$$ S and t $${\in}$$ T, there is a path from s to a terminating vertex as well as a path from a starting vertex to t. This problem can easily be proven NP-hard. For solving the minimum Steiner network problem, we first present an algorithm that runs in time and space that both are polynomial in n with constant degrees, but exponential in \|S\|+\|T\|, where n is the number of vertices in G. Then we present an algorithm that uses space that is quadratic in n and runs in time that is polynomial in n with a degree O(max {max {\|S\|,\|T\|}−2,min {\|S\|,\|T\|}−1}). In spite of this degree, we prove that the number of Steiner vertices in our solution can be as large as \|S\|+\|T\|−2. Our algorithm can enumerate all possible optimal solutions. The input graph G can either be undirected or directed acyclic. We also give a linear time algorithm for the special case when min {\|S\|,\|T\|} = 1 and max {\|S\|,\|T\|} = 2.The minimum union paths problem is similar to the minimum Steiner network problem except that we are given a set H of hitting vertices in G in addition to the sets of starting and terminating vertices. We want to find a subgraph of G with the minimum total edge weight such that the conditions required by the minimum Steiner network problem are satisfied as well as the condition that every hitting vertex is on a path from a starting vertex to a terminating vertex. Furthermore, G must be directed acyclic. For solving the minimum union paths problem, we also present algorithms that have a time and space tradeoff similar to algorithms for the minimum Steiner network problem. We also give a linear time algorithm for the special case when \|S\| = 1, \|T\| = 1 and \|H\| = 2.
Starting Page	101
Ending Page	120
Page Count	20
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	9
Issue Number	1
e-ISSN	15732886
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2005-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	minimum Steiner network minimum union paths directed acyclic graph NP-hard polynomial time Theory of Computation Mathematical Modeling and Industrial Mathematics Combinatorics Convex and Discrete Geometry Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the clustered Steiner tree problem

On the minimum routing cost clustered tree problem

A practical greedy approximation for the directed Steiner tree problem

The minimum vulnerability problem on specific graph classes

Strong minimum energy $$2$$ -hop rooted topology for hierarchical wireless sensor networks

Efficient reassembling of graphs, part 1: the linear case

Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks

Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem

Augmenting weighted graphs to establish directed point-to-point connectivity

Two Variations of the Minimum Steiner Problem

Similar Documents

On the clustered Steiner tree problem

On the minimum routing cost clustered tree problem

A practical greedy approximation for the directed Steiner tree problem

The minimum vulnerability problem on specific graph classes

Strong minimum energy $$2$$ -hop rooted topology for hierarchical wireless sensor networks

Efficient reassembling of graphs, part 1: the linear case

Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks

Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem

Augmenting weighted graphs to establish directed point-to-point connectivity

Two Variations of the Minimum Steiner Problem