The Line Connectivity Problem

Ralf Borndörfer (), Marika Neumann () and Marc E. Pfetsch ()
Additional contact information
Ralf Borndörfer: Zuse Institute Berlin
Marika Neumann: Zuse Institute Berlin
Marc E. Pfetsch: Zuse Institute Berlin

Chapter 90 in Operations Research Proceedings 2008, 2009, pp 557-562 from Springer

Abstract: Summary This paper introduces the line connectivity problem, a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities

Keywords: Polynomial Time; Terminal Node; Steiner Tree Problem; Line Planning; Passenger Trip (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-00142-0_90

Ordering information: This item can be ordered from
http://www.springer.com/9783642001420

DOI: 10.1007/978-3-642-00142-0_90

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().