Conflict-free graph orientations with parity constraints

Details Conflict-free graph orientations with parity constraints Conflict-free graph orientations with parity constraints

2012-03-15

arxiv.org/abs/1203.3256v2

Computer Science

Computational Geometry

To appear, Sixth International Conference on Fun with Algorithms, June 4-6, 2012; 15 pages, 6 figures

Scientific paper

It is known that every multigraph with an even number of edges has an even orientation (i.e., all indegrees are even). We study parity constrained graph orientations under additional constraints. We consider two types of constraints for a multigraph G=(V,E): (1) an exact conflict constraint is an edge set C in E and a vertex v in V such that C should not equal the set of incoming edges at v; (2) a subset conflict constraint is an edge set C in E and a vertex v in V such that C should not be a subset of incoming edges at v. We show that it is NP-complete to decide whether G has an even orientation with exact or subset conflicts, for all conflict sets of size two or higher. We present efficient algorithms for computing parity constrained orientations with disjoint exact or subset conflict pairs.

Affiliated with

Also associated with

No associations

Rating

Conflict-free graph orientations with parity constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conflict-free graph orientations with parity constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conflict-free graph orientations with parity constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-30175