85
Views
10
CrossRef citations to date
0
Altmetric
Section A

General-demand disjoint path covers in a graph with faulty elements

&
Pages 606-617 | Received 13 Jul 2011, Accepted 09 Jan 2012, Published online: 13 Feb 2012
 

Abstract

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.

2010 AMS Subject Classifications :

Acknowledgements

We are grateful to the anonymous reviewers for their comments and suggestions. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2008-521-D00363).

Log in via your institution

Log in to Taylor & Francis Online

PDF download + Online access

  • 48 hours access to article PDF & online version
  • Article PDF can be downloaded
  • Article PDF can be printed
USD 61.00 Add to cart

Issue Purchase

  • 30 days online access to complete issue
  • Article PDFs can be downloaded
  • Article PDFs can be printed
USD 1,129.00 Add to cart

* Local tax will be added as applicable

Related Research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.