Note: The references are not ordered alphabetically!
1100 |
R.M. McConnell, J.P. Spinrad Modular decomposition and transitive orientation Discrete Math. 201 (1999) 189-241 ZMath 0933.05146 |
1101 |
J. Edmonds Path, trees and flowers Canad. J. Math. 17 (1965) 449-467 ZMath 0132.20903 |
1102 |
E. Balas, C.S.Yu On graphs with polynomially solvable maximum weight clique problem Networks 19 (1989) 247-253 ZMath 0661.05036 |
1103 |
A. Brandstaedt, P.L Hammer On the stability number of claw-free, P_5-free and more general graphs. Rutcor Research Report 27-97 1997 ZMath 01340633 |
1104 |
V.V. Lozin Conic reduction of graphs for the stable set problem. Discrete Math. 222 (2000) 199-211 ZMath 0962.05057 |
1105 |
M.C. Golumbic, P.L Hammer Stability in circular arc graphs. J. Algorithms 9 (1988) 56-63 ZMath 0651.68083 |
1106 |
W.L. Hsu, J.P. Spinrad Independent sets in circular arc graphs J. Algorithms 19 (1995) 145-160 ZMath 0839.68069 |
1107 |
N.V.R. Mahadev Vertex deletion and stability number Research report ORWP 90/2 Dept. of Mathematics, Swiss Fed.Inst. of Technology 1990 |
1108 |
V.E. Alekseev On the local restrictions effect on the complexity of finding the graph independence number Combinatorial-algebraic methods in applied mathematics Gorkiy Univ. Press, Gorkiy (1983) 3-13 (in Russian) |
1109 |
V. Giakoumakis, I. Rusu Weighted parameters in (P_5,\overline{P_5})-free graphs Discrete Appl. Math. 80 (1997) 255-261 ZMath 0903.05045 |
1110 |
R. Mosca Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs Information Processing Letters 61 (1997) 137-144 |
1111 |
S. Poljak A note on the stable sets and coloring of graphs Comment. Math. Univ. Carolin. 15 (1974) 307-309 ZMath 0284.05105 |
1112 |
C. Arbib, R. Mosca The stable set problem in (P_5,diamond)-free graphs Tech. Report 79, Univ. di L'Aquila, Dipartamento di Matematics Pure e Applicata 1995 |
1113 |
V.V. Lozin Stability in P_5 and banner-free graphs European J. Oper. Research, to appear. ZMath 0952.90042 |
1114 |
A. Hertz On a graph transformation that preserves the stability number Research report ORWP 97/11 Dept. of Math., Swiss Fed. Inst. of Tech. 1997. Or: Yugosl. J. Oper. Res. 10, No.1, 1-12 (2000). [ISSN 0354-0243] ZMath 0946.05080 |
1115 |
D.G. Corneil The complexity of generalized clique packing Discrete Appl. Math. 12 (1985) 233-240 ZMath 0588.05037 |
1116 |
V.E. Alekseev, V.V. Lozin Independent sets of maximum weight in (p,q)-colorable graphs Rutcor Research Report 12-2002 ZMath 1034.05020 |
1117 |
A. Brandstaedt, V.V. Lozin A note on \alpha-redundant vertices in graphs. Discrete Appl. Math. 108 (2001) 301-308 ZMath 0968.05058 |
1118 |
M.U. Gerber, V.V. Lozin On the stable set problem in special P_5-free graphs. Rutcor Research Report 24-2000 ZMath 1028.05103 |
1119 |
R. Hayward, J. Spinrad. R. Sritharan Weakly chordal graph algorithms via handles Proc. of the 11th symposium on Discrete Algorithms 42-49, 2000 ZMath 0956.68104 |
1120 |
S. Felsner, R. Muller, L. Wernisch Trapezoid graphs and generalizations, geometry and algorithms Discrete Appl. Math. 74 13-32 (1997) ZMath 0877.68093 |
1121 |
A. Apostolico, M.J. Atallah, S.E. Hambrusch New clique and independent set algorithms for circle graphs. Discrete Appl. Math 36 (1992) 1-24 Erratum: Discrete Appl. Math 41 (1993) 179-180 ZMath 0794.05120 |
1122 |
C.S. Rim, K. Nakajima On rectangle intersection and overlap graphs, IEEE Trans. Circuits Systems/Fund. Theory Appl. 42 549-553, 1995 ZMath 0838.68089 |
1123 |
E. Cenek, L. Stewart Maximum independent set and maximum clique algorithms for overlap graphs Discrete Appl. Math. 131, No.1 77-91 (2003) ZMath 1022.05081 |
1124 |
A. Brandstaedt, C.T. Hoang, V.B. Le Stability number of bull- and chair-free graphs revisited to appear in Discrete Appl. Math. ZMath 1029.05077 |
1125 |
A. Brandstaedt, V.B. Le, H.N. de Ridder Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes. Universitaet Rostock, Fachbereich Informatik, Preprint CS-14-01 |
1126 |
A. Brandstaedt, S. Mahfud Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters 84 (2002) 251-259 ZMath 1042.68085 |
1127 |
A. Brandstaedt, F. Dragan On linear and circular structure of (claw, net)-free graph To appear in Discrete Appl. Math. ZMath 1032.05095 |
1128 |
M. Chudnovsky, N. Robertson, P.D. Seymour, R.Thomas The strong perfect graph theorem Annals of Math. 164 No.1 51-229 (2006) doi 10.4007/annals.2006.164.51 |
1129 |
M. Yannakakis, F. Gavril Edge dominating sets in graphs SIAM J. Appl. Math. 38(3) 364-372, 1980 ZMath 0455.05047 |
1130 | Damaschke, personal communication |
1131 | Hougardy-diagram |
1132 | Jerry Spinrad, personal communication. |
1133 | Every minimal AT is not P_4 extendible (P. Ochem, personal communication) |
1134 |
By maximal degree bound and
[954]
E.R. Scheinerman
Intersection classes and multiple intersection parameters of a graph Ph. D. Thesis, Princeton University 1984 |
1135 |
Giakoumakis, Vassilis; Vanherpe, Jean-Marie Bi-complement reducible graphs Adv. Appl. Math. 18, No.4, 389-402 (1997) ZMath 0872.05031 |
1136 |
Fouquet, J.L; Giakoumakis, Vassilis; Vanherpe, Jean-Marie
Bipartite graphs totally decomposable by canonical decomposition International Journal of Foundations of Computer Science 10 (1999) 135-147 |
1138 |
V.V. Lozin E-free bipartite graphs Discrete Analysis and Operations Research, Ser.1 Vol. 7, No. 1 (2000) 49-66 ZMath 0949.05073 |
1139 |
Lozin, Vadim V. On a generalization of bi-complement reducible graphs. Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893, 528-538 (2000) ZMath 0996.68136 |
1140 |
Lozin, Vadim V. Bipartite graphs without a skew star Rutcor Research Report RRR 20-2001 http://rutcor.rutgers.edu/pub/rrr/reports2001/20.ps ZMath 1010.05067 |
1141 |
A. Brandstaedt, P.L. Hammer, V.B. Le, V.V. Lozin Bisplit graphs Rutcor Research Report RRR 28-2002 http://rutcor.rutgers.edu/pub/rrr/reports2002/28_2002.ps |
1142 |
A.K. Dewdney Fast turing reductions between problems in NP; chapter 4; reductions between NP-complete problems. Technical Report 71, Dept. Computer Science, University of Western Ontario 1981 |
1143 |
M.S. Chang Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27, No.6, 1671-1694 (1998) ZMath 0911.05051 |
1144 |
A.A. Bertossi Dominating sets for split and bipartite graphs. Inform. Process. Lett. 19 (1984) 37-40 ZMath 0539.68058 |
1145 |
D.G. Corneil, Y. Perl Clustering and domination in perfect graphs. Discrete. Appl. Math. 9 (1984) 27-39 ZMath 0581.05053 |
1146 |
K.S. Booth, J.H. Johnson Dominating sets in chordal graphs SIAM J. Comput. 11 (1982) 191-199 ZMath 0485.05055 |
1147 |
M. Farber, J.M. Keil Domination in permutation graphs J. Algorithms 6 (1985) 309-321 ZMath 0598.05056 |
1148 |
K. Tsai, W.L. Hsu Fast algorithms for the dominating set problem on permutation graphs Algorithmica 9 (1993) 601-614 ZMath 0768.68063 |
1149 |
C. Rhee, Y.D. Liang, S.K. Dhall, S. Lakshmivarahan An O(n+m) algorithm for finding a minimum-weight dominating set in a permutation graph SIAM J. Comput. 25 (1996) 404-419 ZMath 0851.68089 |
1150 |
D. Kratsch, L. Stewart Domination on cocomparability graphs SIAM J. Discrete Math. 6(3) (1993) 400-417 ZMath 0780.05032 |
1151 |
H. Breu, D.G. Kirkpatrick Algorithms for the dominating set and Steiner set problems in cocomparability graphs Manuscript 1993 |
1152 |
D. Kratsch Domination and total domination in asteroidal triple-free graphs Discrete Appl. Math. 99 No.1-3, 111-123 (2000) ZMath 0943.05063 |
1153 |
F. Nicolai, T. Szymczak Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs Networks 37,No.3 117-128 (2001) ZMath 0974.05060 |
1154 |
J.M. Keil The complexity of domination problems in circle graphs Discrete Appl. Math. 42 (1993) 51-63 ZMath 0786.05079 |
1155 |
Liang, Y. Daniel Dominations in trapezoid graphs. Inf. Process. Lett. 52, No.6, 309-315 (1994) ZMath 0875.68679 |
1156 |
Mueller, Haiko; Brandstaedt, Andreas The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theor. Comput. Sci. 53, 257-265 (1987) ZMath 0638.68062 |
1157 |
H. Hempel, D. Kratsch On claw-free asteroidal triple-free graphs Discrete Appl. Math. 121, No.1-3, 155-180 (2002) ZMath 1002.68109 |
1158 |
Hsu, Wen-Lian; Tsai, Kuo-Hui Linear time algorithms on circular-arc graphs. Inf. Process. Lett. 40, No.3, 123-129 (1991) ZMath 0748.68044 |
1159 |
F. Gavril Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73(5-6) 181-188 (2000) |
1160 |
M. Farber On diameters and radii of bridged graphs. Discrete Math. 73 (1989) 249-260 ZMath 0667.05036 |
1161 |
A. Brandstaedt, R. Mosca On the structure and stability number of P_5 and co-chair-free graphs. To appear in Discrete Appl. Math. ZMath 1029.05142 |
1162 |
Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry Generalized planar matching. J. Algorithms 11, No.2, 153-184 (1990) ZMath 0731.68041 |
1163 |
Hare, E.O.; Hedetniemi, S.T.; Hare, W.R. Algorithms for computing the domination number of k$\times n$ complete grid graphs. Combinatorics, graph theory, and computing, Proc. 17th Southeast. Conf., Boca Raton/Fl. 1986, Congr. Numerantium 55, 81-92 (1986) ZMath 0637.68077 |
1164 |
V. Kamakoti, C. Pandu Rangan Efficient Transitive Reduction on Permutation Graphs and its Applications. CSI JL on Computer Science and Informatics, Vol. 23, No. 3, pp. 52 - 59 (1993) |
1165 |
A. Brandstaedt, D. Kratsch On the restriction of some NP-complete graph problems to permutation graphs. Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985) ZMath 0575.68069 |
1166 |
A. Frank Some polynomial algorithms for certain graphs and hypergraphs. Proc. 5th Br. comb. Conf., Aberdeen 1975, Congr. Numer. XV, 211-226 (1976). ZMath 0328.05141 |
1167 |
Damaschke, Peter; Müller, Haiko; Kratsch, Dieter Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36, No.5, 231-236 (1990) ZMath 0706.68055 |
1168 |
A. Brandstaedt, V.B. Le Split-perfect graphs: Characterizations and algorithmic use. Preprint CS-02-00 Fachbereich Informatik, Universitaet Rostock 2000 ZMath 0989.05115 |
1169 | By definition. |
1170 |
H. Bodlaender, A. Brandstaedt, D. Kratsch, M. Rao, J. Spinrad Linear time algorithms for some NP-complete problems on (P_5, gem)-free graphs. Manuscript 2003 |
1171 |
A. Brandstaedt, D. Kratsch On the structure of (P_5,gem)-free graphs. Manuscript 2002 |
1172 |
J. Mark Keil, P. Belleville Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs. Discrete Appl. Math. 140, No.1-3, 73-89 (2004). [ISSN 0166-218X] ZMath 02083770 |
1173 |
D. Nakamura, A. Tamura A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph J. Oper. Res. Soc. Japan 44 (2001) no.2 194-204 ZMath 01918579 |
1174 |
B. Courcelle, S. Olariu Upper bounds to the clique-width of graphs. Discrete Appl. Math. 101 (2000) 77-114 ZMath 0958.05105 |
1175 |
B. Courcelle, J.A. Makowsky, U. Rotics Linear time optimization problems on graphs of bounded clique width. Theory of Computing Systems 33 (2000) 125-150 |
1176 |
J.A. Makowsky, U. Rotics On the clique-width of graphs with few $P_4$'s. International Journal of Foundations of Computer Science 10 (1999) 329-348 |
1177 |
Golumbic, Martin Charles; Rotics, Udi On the clique-width of perfect graph classes (extended abstract) . Graph theoretic concepts in computer science. 25th international workshop, WG '99 Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 135-147 (1999) ZMath 0941.05047 |
1178 |
Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi Polynomial time recognition of clique-width $\leq 3$ graphs (extended abstract). Gonnet, Gastón H. (ed.) et al., LATIN 2000: Theoretical informatics. 4th Latin American symposium, Punta del Este, Uruguay, April 10-14, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1776, 126-134 (2000) ZMath 0961.05062 |
1179 |
J.M. Vanherpe Clique-width of partner-limited graphs. International Conference of Graph Theory, Marseille 2000 ZMath 1031.05113Manuscript. |
1180 |
F. Roussel, I. Rusu, H. Thuillier On graphs with limited number of P_4-partners. International Journal of Foundations of Computer Science, 1o 103-121 (1999) |
1181 |
V. Giakoumakis, J.M. Vanherpe Linear time recognition and optimization for weak-bisplit graphs, bi-cographs and bipartite P_6-free graphs. Manuscript, 2001 |
1182 |
A. Brandstaedt, V.V. Lozin On the linear structure and clique-width of bipartite permutation graphs. Accepted for Ars Combinatorica Available as Rutcor Research report RRR 29-2001 here |
1183 |
R. Boliac, V.V. Lozin On the clique-width of graphs in hereditary classes. Rutcor Research Report RRR 14-2002 ZMath 1020.05046Available as Rutcor Research report RRR 14-2002 here |
1184 |
A. Brandstaedt, H.-O. Le, J.M. Vanherpe Structure and stability number of (chair, co-P, gem)-free graphs. Manuscript 2001 |
1185 |
A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca New graph classes of bounded clique-width WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002) ZMath 1022.68090 |
1186 |
A. Brandstaedt, R. Mosca On variations of P_4-sparse graphs. Manuscript 2001 ZMath 1022.05069 |
1187 |
J.-L. Fouquet A decomposition for a class of (P_5, \overline{P_5})-free graphs. Discrete Math. 121 (1993) 19-30 ZMath 0784.68066 |
1188 |
A. Brandstaedt, H.-O. Le, R. Mosca (gem, co-gem)-free graphs have bounded clique-width Manuscript 2002 |
1189 |
A. Brandstaedt, H.-O. Le, R. Mosca Chordal co-gem-free graphs have bounded clique-width Manuscript 2002 |
1190 |
A. Brandstaedt (P_5,diamond)-free graphs revisited: Structure and linear time optimization. Accepted for Discrete Appl. Math. ZMath 02062809 |
1191 |
Hammer, Peter L.; Peled, Uri N.; Sun, Xiaorong Difference graphs. Discrete Appl. Math. 28, No.17, 35-44 (1990) ZMath 0716.05032 |
1192 |
V. Lozin, D. Rautenbach Chordal bipartite graphs of bounded tree- and clique-width. Rutcor Research Report 2-2003 ZMath 02083728Available here. |
1193 |
Hoàng, Chính T.; Maffray, Frédéric; Noy, Marc A characterization of $P_4$-indifference graphs. J. Graph Theory 31, No.3, 155-162 (1999) ZMath 0929.05073 |
1194 |
Elaine M. Eschen, Julie L. Johnson, Jeremy P. Spinrad, R. Sritharan Recognition of some perfectly orderable graph classes. Discrete Appl. Math. 128, No.2-3, 355-373 (2003). [ISSN 0166-218X] ZMath 1019.68075 |
1195 |
A. Kostochka, J. Kratochvil Covering and coloring polygon-circle graphs. Discrete Math. 163 299-305 (1997) ZMath 0871.05025 |
1196 |
E.W. Cenek Subtree overlap graphs and the maximum independent set problem Master's thesis, Dept. of Computer Science, University of ALberta 1998 |
1197 | Pascal Ochem, personal communication |
1198 |
P. Zhang Probe interval graphs and it application to physical mapping of DNA Manuscript, 1994 |
1199 |
Johnson, Julie L.; Spinrad, Jeremy P. A polynomial time recognition algorithm for probe interval graphs. Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms. 477-486 (2001) ZMath 0988.05086 |