http:^^www.cs.usask.ca^projects^graph^index.shtml
来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 71 行
SHTML
71 行
Date: Tue, 26 Nov 1996 00:57:45 GMT
Server: NCSA/1.5.1
Content-type: text/html
<HTML><HEAD><TITLE>Graph Theory</TITLE></HEAD><BODY><H1>Graph Theory </H1> <P> Primary Investigators: <!WA0><AHREF="http://www.cs.usask.ca/homepages/faculty/cheston/Cheston.html"> Grant Cheston </A>and <!WA1><A HREF="http://www.cs.usask.ca/homepages/faculty/keil/Keil.html"> Mark Keil </A> <H2> Algorithmic Development in Restricted Classes of Graphs</H2><P>Many problems in graph theory are NP-complete on general graphs. Inpractice one rarely has to contend with general graphs; ofteninformation is available to limit the graphs to a restricted class. Inparticular, graphs which arise from geometric models are common. Alsothere are problems that can be solved efficiently for some of these restrictedclasses (for example, maximum clique in circle graphs). In this project weemploy various techniques including a generalized form of dynamicprogramming to design polynomial time algorithms for problems on variousrestricted classes of graphs. </P><P>Sometimes graph parameters that are not generally equal are equalfor certain restricted classes . This can be useful in showing theproblems are NP-complete or in developing algorithms. Finally, it isuseful to study new classes of graphs, and determine for a wide varietyof problems whether they are NP-complete or not . </P></P><H2> Even Adjacency Split of a Graph </H2><P>The objective is to partition the vertices of a graph into two setsS and T such that each vertex of one set is adjacent to a vertex in theother set, and the two sets are within one of having the same size.Determining whether a graph has an Even Adjacency Split (EAS) isNP-complete for general graphs. Nevertheless there is an O(n<sup>2</sup>)algorithm for trees, and a linear time algorithm has been found thathandles graphs where no vertex is adjacent to more than two vertices ofdegree 1. </P></P><H2> Fractional Graph Parameters </H2><P>For some time, it has been useful to describe graphs in terms of avariety of parameters, for example the chromatic number, the cliquenumber, the independence number, the matching number, and the dominationnumber. All these parameters can be expressed in terms of integerfunctions on the graphs. Recently several people have started toinvestigate fractional variations of these parameters where thefunctions map to the [0,1] real interval rather than the set ofintegers. This project has been investigating the Upper FractionalDomination Number, GAMMA<SUB>f</SUB>. We have shown that GAMMA<SUB>f</SUB> isalways computable and rational, but in general it is NP-hard to computeit. For trees, cycles, simplicial graphs, and 2-trees, we have shownthat GAMMA<SUB>f</SUB> = GAMMA (the corresponding integer problem), and this value is easy to compute. Also we have shown that for a large subclass of the class of PerfectGraphs (the subclass is called the Strongly Perfect Graphs), fourparameters are equal. These four parameters are beta, GAMMA,GAMMA<SUB>f</SUB>, and IR, where beta is theIndependence number and IR is the Upper Irredundance number. Otherclasses of graphs have also been studied todetermine whether these parameters are equal, but generally they arenot equal. </P></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?