古老
发表于 2025-4-1 05:44:47
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.
大约冬季
发表于 2025-4-1 08:48:21
http://reply.papertrans.cn/39/3881/388019/388019_62.png
MOTIF
发表于 2025-4-1 11:46:31
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.
窒息
发表于 2025-4-1 17:19:17
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.