Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Circuit covers in series-parallel mixed graphs

Orlando LeeContact Information and Yoshiko WakabayashiContact Information

(1)  Instituto de Matemática e Estatística, Universidade de SÃo Paulo, Rua do MatÃo 1010, 05508-900 SÃo Paulo, SP, Brazil
Abstract
A mixed graph is a graph that contains both edges and arcs. Given a nonnegative integer weight function p on the edges and arcs of a mixed graph M, we wish to decide whether (M,p) has a circuit cover, that is, if there is a list of circuits in M such that every edge (arc) e is contained in exactly p(e) circuits in the list. When M is a directed graph or an undirected graph with no Petersen graph as a minor, good necessary and sufficient conditions are known for the existence of a circuit cover. For general mixed graphs this problem is known to be NP-complete. We provide necessary and sufficient conditions for the existence of a circuit cover of (M, p) when M is a series-parallel mixed graph, that is, the underlying graph of M does not have Ka as a minor. We also describe a polynomial-time algorithm to find such a circuit cover, when it exists. Further, we show that p can be written as a nonnegative integer linear combination of at most m incidence vectors of circuits of M, where m is the number of edges and arcs. We also present a polynomial-time algorithm to find a minimum circuit in a series-parallel mixed graph with arbitrary weights. Other results on the fractional circuit cover and the circuit double cover problem are discussed.
This work has been partially supported by FAPESP (Proc. 96/04505-2), CNPq (Proc. 304527/89-0), CAPES (Proc. 3302006-0) and PRONEX (Project 107/97).

Contact Information Orlando Lee
Email: lee@ime.usp.br

Contact Information Yoshiko Wakabayashi
Email: yw@ime.usp.br
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)