“Circular-arc graph”的意思、由来-开放百科全书

词条

Circular-arc graph

释义

Recognition
Relation to other graph classes
Some subclasses
Unit circular-arc graphs Proper circular-arc graphs Helly circular-arc graphs
Applications
Notes
References
External links

In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect.

Formally, let

be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where

and

A family of arcs that corresponds to G is called an arc model.

Recognition

{{harvtxt|Tucker|1980}} demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in

time. {{harvtxt|McConnell|2003}} gave the first linear

time recognition algorithm. More recently, Kaplan and Nussbaum^[1] developed a simpler linear time recognition algorithm.

Relation to other graph classes

Circular-arc graphs are a natural generalization of interval graphs. If a circular-arc graph G has an arc model that leaves some point of the circle uncovered, the circle can be cut at that point and stretched to a line, which results in an interval representation. Unlike interval graphs, however, circular-arc graphs are not always perfect, as the odd chordless cycles C₅, C₇, etc., are circular-arc graphs.

Some subclasses

In the following, let be an arbitrary graph.

Unit circular-arc graphs

is a unit circular-arc graph if there exists a corresponding arc model such that each arc is of equal length.

The number of labelled unit circular-arc graphs on n vertices is given by .

^[2]

Proper circular-arc graphs

is a proper circular-arc graph (also known as a circular interval graph)^[3] if there exists a corresponding arc model such that no arc properly contains another. Recognizing these graphs and constructing a proper arc model can both be performed in linear

time.^[4]

They form one of the fundamental subclasses of the claw-free graphs.^[3]

Helly circular-arc graphs

is a Helly circular-arc graph if there exists a corresponding arc model such that the arcs constitute a Helly family. {{harvtxt|Gavril|1974}} gives a characterization of this class that implies an recognition algorithm.

{{harvtxt|Joeris|Lin|McConnell|Spinrad|2009}} give other characterizations of this class, which imply a recognition algorithm that runs in O(n+m) time when the input is a graph. If the input graph is not a Helly circular-arc graph, then the algorithm returns a certificate of this fact in the form of a forbidden induced subgraph. They also gave an O(n) time algorithm for determining whether a given circular-arc model has the Helly property.

Applications

Circular-arc graphs are useful in modeling periodic resource allocation problems in operations research. Each interval represents a request for a resource for a specific period repeated in time.

Notes

1. ^{{Cite journal|last=Kaplan|first=Haim|last2=Nussbaum|first2=Yahav|date=2011-11-01|title=A Simpler Linear-Time Recognition of Circular-Arc Graphs|journal=Algorithmica|language=en|volume=61|issue=3|pages=694–737|doi=10.1007/s00453-010-9432-y|issn=0178-4617|citeseerx=10.1.1.76.2480}}
2. ^{{cite journal |last1=Alexandersson |first1=Per |last2=Panova |first2=Greta |title=LLT polynomials, chromatic quasisymmetric functions and graphs with cycles |journal=Discrete Mathematics |date=December 2018 |volume=341 |issue=12 |pages=3453–3482 |doi=10.1016/j.disc.2018.09.001}}
3. ^¹Described with a different but equivalent definition by {{harvtxt|Chudnovsky|Seymour|2008}}.
4. ^{{harvtxt|Deng|Hell|Huang|1996}} pg. ?

References

{{citation

| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
| doi = 10.1016/j.jctb.2008.03.001
| issue = 4
| journal = Journal of Combinatorial Theory
| mr = 2418774
| pages = 812–834
| series = Series B
| title = Claw-free graphs. III. Circular interval graphs
| url = http://www.columbia.edu/~mc2775/claws3.pdf
| volume = 98
| year = 2008}}.

{{citation

| last1 = Deng | first1 = Xiaotie
| last2 = Hell | first2 = Pavol | author2-link = Pavol Hell
| last3 = Huang | first3 = Jing
| title = Linear-Time representation algorithms for proper circular-arc graphs and proper interval graphs
| journal = SIAM Journal on Computing
| volume = 25 | year = 1996 | issue = 2 | pages = 390–403
| doi = 10.1137/S0097539792269095}}.

{{citation

| last = Gavril | first = Fanica
| title = Algorithms on circular-arc graphs
| journal = Networks
| volume = 4 | year = 1974 | issue = 4 | pages = 357–369
| doi = 10.1002/net.3230040407}}.

{{citation

}}. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

{{citation

{{citation

{{citation

| last = Tucker | first = Alan |authorlink=Alan Tucker
| title = An efficient test for circular-arc graphs
| journal = SIAM Journal on Computing
| volume = 9 | year = 1980 | issue = 1 | pages = 1–24
| doi = 10.1137/0209001}}.

External links

Circular arc graph, Information System on Graph Class Inclusions

2 : Intersection classes of graphs|Geometric graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。