Graded Sparse Graphs and Matroids

Details Graded Sparse Graphs and Matroids Graded Sparse Graphs and Matroids

2007-11-19

arxiv.org/abs/0711.2838v2

Journal of Universal Computer Science, vol. 13, no. 10, (2007)

Mathematics

Combinatorics

9 pages, 1 figure; improved presentation and fixed typos

Scientific paper

Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {\bf graded sparse graphs}, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: {\bf Decision}, {\bf Extraction}, {\bf Components}, {\bf Optimization}, and {\bf Extension}. We extend our {\bf pebble game algorithms} to solve them.

Affiliated with

Also associated with

No associations

Rating

Graded Sparse Graphs and Matroids 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 Graded Sparse Graphs and Matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graded Sparse Graphs and Matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115514