| 词条 | Graph sandwich problem |
| 释义 |
In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph. Graph sandwich problems generalize the problem of testing whether a given graph belongs to a family of graphs, and have attracted attention because of their applications and as a natural generalization of recognition problems.[1] Problem statementMore precisely, given a vertex set V, a mandatory edge set E1, and a larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1 = (V, E1), G2 = (V, E2) if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows:[2][3] Graph Sandwich Problem for Property Π: Instance: Vertex set V and edge sets E1 ⊆ E2 ⊆ V × V. Question: Is there a graph G = (V, E) such that E1 ⊆ E ⊆ E2 and G satisfies property Π ? The recognition problem for a class of graphs (those satisfying a property Π) is equivalent to the particular graph sandwich problem where E1 = E2, that is, the optional edge set is empty. Computational complexityThe graph sandwich problem is NP-complete when Π is the property of being a chordal graph, comparability graph, permutation graph, chordal bipartite graph, or chain graph.[2][4] It can be solved in polynomial time for split graphs,[2][5] threshold graphs,[2][5] and graphs in which every five vertices contain at most one four-vertex induced path.[6] The complexity status has also been settled for the H-free graph sandwich problems for each of the four-vertex graphs H.[7] References1. ^{{citation|last1=Golumbic|first1=Martin Charles|last2=Trenk|first2=Ann N. |title=Tolerance Graphs|publisher=Cambridge|year=2004|contribution=Chapter 4. Interval probe graphs and sandwich problems|pages=63–83}}. 2. ^1 2 3 {{citation | last1=Golumbic|first1=Martin Charles | last2 = Kaplan | first2 = Haim | last3 = Shamir | first3 = Ron | journal = J. Algorithms | pages = 449–473 | title = Graph sandwich problems | volume = 19 | year = 1995 | doi=10.1006/jagm.1995.1047}}. 3. ^{{citation|first=Martin Charles|last=Golumbic|authorlink=Martin Charles Golumbic|title=Algorithmic Graph Theory and Perfect Graphs|edition=2nd|year=2004|series=Annals of Discrete Mathematics|volume=57|publisher=Elsevier|page=279|url=https://books.google.com/books?id=8xo-VrWo5_QC&pg=PA279}}. 4. ^{{citation | last1 = de Figueiredo | first1 = C. M. H. | last2 = Faria | first2 = L. | last3 = Klein | first3 = S. | last4 = Sritharan | first4 = R. | doi = 10.1016/j.tcs.2007.04.007 | issue = 1-3 | journal = Theoretical Computer Science | mr = 2347393 | pages = 57–67 | title = On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs | volume = 381 | year = 2007}}. 5. ^1 {{citation|last1=Mahadev|first1=N.V.R.|last2=Peled|first2=Uri N.|title=Threshold Graphs and Related Topics|series=Annals of Discrete Mathematics|volume=57|publisher=North-Holland|year=1995|pages=19–22|url=https://books.google.com/books?id=nWfGo_VX5M8C&pg=PA19}}. 6. ^{{citation | last1 = Dantas | first1 = S. | last2 = Klein | first2 = S. | last3 = Mello| first3 = C.P. | last4 = Morgana| first4 = A. | doi = 10.1016/j.disc.2008.01.014 | journal = Discrete Mathematics | pages = 3664–3673 | title = The graph sandwich problem for P4-sparse graphs | volume = 309 | year = 2009}}. 7. ^{{citation | last1=Dantas|first1=Simone | last2 = de Figueiredo| first2 = Celina M.H. | last3 = Maffray| first3 = Frédéric | last4 = Teixeira| first4 = Rafael B. | journal = Discrete Applied Mathematics | pages = Available online 11 October 2013 | title = The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem | volume = | year = 2013 | doi=10.1016/j.dam.2013.09.004}}. Further reading
| last1=Dantas|first1=Simone | last2 = de Figueiredo| first2 = Celina M.H. | last3 = da Silva| first3 = Murilo V.G. | last4 = Teixeira| first4 = Rafael B. | doi = 10.1016/j.dam.2010.11.010 | journal = Discrete Applied Mathematics | pages = 1717-1725 | title = On the forbidden induced subgraph sandwich problem | volume = 159 | year = 2011 }}. 1 : Computational problems in graph theory |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。