User:BIOalgorithm/sandbox: Difference between revisions

Revision as of 00:12, 13 July 2012

Latest revision as of 16:00, 17 May 2021

(3 intermediate revisions by 2 users not shown)

Line 99:

* Test each S-prime component to see if it is an interval graph.

:This can be done by truly building the truecorresponding interval graph; first adding the non-simplicial vertices, then adding the simplicial vertices through a linear scan. The second part is intuitive; the first part needs more detailed discussion.

'''Lemma'''

Let u_k be the next interval to be placed, which is not a neighbor of previously chosen intervals. Let u_j be the parent of u_k and u_i be the parent of u_j in the BFS-tree. It can be determined uniquely which endpoints of u_j or u_i is contained in u_k.

There are three cases, place each edge according to its category.

* Case 1: (f(u_i), u_j) ∉ E. If u_i ,u_k are on the different side of u_j, u_k would contain u_j.

* Case 2: (f(u_k), u_j ) ∉ E. Again, if u_i, u_k are on the different side of u_j, u_k would contain u_j.

* Case 3: (f(u_j), u_k) ∉ E and (f(u_j), u_i) ∉ E. If u_i ,u_k are on the different sides of u_j, u_k cannot be adjacent to u_i.

:(''f''(''u'') := ''u'''s neighbor vertex with the smallest ''π''-index.)

==Related families of graphs==

Line 147 ⟶ 156:

| title = A partial ''k''-arboretum of graphs with bounded treewidth

| volume = 209

| year = 1998| hdl = 1874/18312 }}.

*{{citation

| last = Hsu | first = W. L.

| issue = 11-1611–16

| journal = [[Lecture Notes in Computer Science]]

| title = A new test for interval graphs

Line 164 ⟶ 173:

| doi = 10.1016/S0022-0000(76)80045-1

| issue = 3}}.

* {{cite book|year=1978|last=Cohen|first=Joel E.|authorlink=Joel E. Cohen|title=Food webs and niche space|series=Monographs in Population Biology|volume=11|___location=Princeton, NJ|publisher=[http://press.princeton.edu/titles/324.html Princeton University Press]|pages=xv+1–190|ref=harv|isbn=978-0-691-08202-8}}

*{{citation

| last = Eckhoff | first = Jürgen

Line 186 ⟶ 195:

| year = 1997

| mr = 1432221}}.

* {{cite book|last=Fishburn|first=Peter C.|authorlink=Peter C. Fishburn|year=1985|title=Interval orders and interval graphs: A study of partially ordered sets|series=Wiley-Interscience Series in Discrete Mathematics|___location=New York|publisher=John Wiley & Sons|ref=harv|mr=|isbn=}}

*{{citation

| author1-link = D. R. Fulkerson | last1 = Fulkerson | first1 = D. R. | last2 = Gross | first2 = O. A.

Line 193 ⟶ 202:

| volume = 15

| pages = 835–855

| year = 1965| issue = 3 | doi = 10.2140/pjm.1965.15.835 }}.

*{{citation

| last1 = Gilmore | first1 = P. C.

Line 215 ⟶ 224:

| volume = 40

| pages = 1108–1133

| year = 1993| doi = 10.1145/174147.169675 }}.

*{{citation

| last1 = Habib | first1 = Michel | last2 = McConnell | first2 = Ross

Line 224 ⟶ 233:

| pages = 59–84

| year = 2000

| issue = 1–2 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps

| doi = 10.1016/S0304-3975(97)00241-7}}.

*{{citation

Line 236 ⟶ 245:

| year = 1994

| pages = 309–317

| doi = 10.1093/bioinformatics/10.3.309| pmid = 7922688 }}.

== External links ==

Line 245 ⟶ 254:

* {{mathworld | urlname = IntervalGraph | title = Interval graph}}

<!-- Comment out categories and interwikis while this is in userspace

{{DEFAULTSORT:Interval Graph}}

[[Category:Perfect graphs]]

Line 254 ⟶ 264:

[[hu:Intervallumgráf]]

[[pl:Graf przedziałowy]]

-->