Affordable Access

Publisher Website

Steiner Networks with unicyclic connected components

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
36
Identifiers
DOI: 10.1016/j.endm.2010.05.123
Keywords
  • Cycles
  • Networks
  • Bicircular Matroid
  • Polyhedra
  • Unicyclic Graphs
  • Steiner
Disciplines
  • Computer Science
  • Design

Abstract

Abstract This paper focuses on the design of minimum cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of the perfect binary 2-matching problem. It turns out that the problem is easy to solve since it can be seen as a b-matching in an appropriate extended graph. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg-Rao algorithm to separate blossom inequalities.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Networks with unicyclic connected components and w...

on Electronic Notes in Discrete M... Jan 01, 2010

Bounding component sizes of two-connected Steiner...

on Information Processing Letters Jan 01, 2007

Two-connected Steiner networks: structural propert...

on Operations Research Letters Jan 01, 2005
More articles like this..