Titlebook: ;

古老

Minus Domination in Small-Degree Graphs, section is concerned with complexity results for Δ ≤ 4: We show that computing .. is NP-hard and MAX SNP-hard there, but that .. can be approximated in linear time within some constant factor. Finally, our approach also applies to signed domination (where the labels are -1,+1 only) in small-degree graphs.

大约冬季

MOTIF

A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In a compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteroidal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.

窒息

Rankings of Directed Graphs,d that it can be computed in polynomial time. Unlike the undirected case, however, deciding whether the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard.