logo
科言猫学术研究的AI总结
language
手机端手机端
  • Phone Feature微信小程序
简体中文简体中文
notice消息通知
博客博客
delete
arrow
返回

Thick Forests

delete2026-01-01
delete0
delete
OA
AI
M
Martin Dyer
H
Haiko Müller *
DOI：10.1016/j.dam.2025.12.042delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
我们考虑一类称为厚图的图，其顶点由对应稀疏图的团替代，边由反二分图替代。特别地，我们考虑厚森林的情况，并证明其为最大一类完美厚图。识别厚C-图类成员的问题在类C非三角形时为NP完全问题，因此我们专注于此情况。即便如此，成员识别仍可能为NP完全问题。然而，我们证明厚森林类的识别可在多项式时间内完成。我们考虑厚图上的两个经典组合问题：独立集和恰当着色。由于确定完美图的独立数或色数的复杂性已知为易解的，我们考察厚森林中所有独立集和着色数的计算复杂性。最后，我们考虑厚图更大类别的两个参数化扩展：参数为稀疏图大小时，以及参数为其树宽时。(c) 2025 作者。由Elsevier B.V.出版。本文为开放获取文章，采用CC BY许可（http://creativecommons.org/licenses/by/4.0/）。
Keyword:
Counting
FPRAS
Unipolar graph
AI总结

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

D
Discrete Applied Mathematics
IF:
1.1
论文数:
336
被引数:
7.7K

机构

U
university of leeds
学者数:
3.6W
论文数: 3.3W
被引数: 45
引用论文

引用论文

The complexity of generalized graph colorings
errDiscrete Applied Mathematics
IF0
err1996-08-01
err0
PREAI
errBrown,Jason I.
err分享
err收藏
Geometric Algorithms and Combinatorial Optimization
errAlgorithms and Combinatorics
IF0
err1988-01-01
err0
PREAI
errMartin Grötschel; László Lovász; Alexander Schrijver
err分享
err收藏
Computing the Minimum Fill-In is NP-Complete
errSIAM Journal on Algebraic Discrete Methods
IF0
err1981-03-01
err0
PREAI
errMihalis Yannakakis
err分享
err收藏
A partial k-arboretum of graphs with bounded treewidth
errTheoretical Computer Science
IF0
err1998-12-01
err0
errOAAI
errHans L. Bodlaender
err分享
err收藏
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
errJournal of the ACM
IF0
err2004-07-01
err0
PREAI
errMark Jerrum; Alistair Sinclair; Eric Vigoda
err分享
err收藏
Algorithmic Aspects of Vertex Elimination on Graphs
errSIAM Journal on Computing
IF0
err1976-06-01
err0
PREAI
errDonald J. Rose; R. Endre Tarjan; George S. Lueker
err分享
err收藏
Complexity of Finding Embeddings in a k-Tree
errSIAM Journal on Algebraic Discrete Methods
IF0
err1987-04-01
err0
PREAI
errStefan Arnborg; Derek G. Corneil; Andrzej Proskurowski
err分享
err收藏
An Introduction to Clique Minimal Separator Decomposition
errAlgorithms
IF0
err2010-05-14
err0
errOAAI
errAnne Berry; Romain Pogorelcnik; Geneviève Simonet
err分享
err收藏
The intersection graphs of subtrees in trees are exactly the chordal graphs
errJournal of Combinatorial Theory, Series B
IF0
err1974-02-01
err0
PREAI
errFǎnicǎ Gavril
err分享
err收藏
Detecting an Odd Hole检测一个奇环
errJournal of the ACM
IF0
err2020-02-29
err0
PREAI
errChudnovsky,Maria; Scott,Alex; Seymour,Paul; Spirkl,Sophie
err分享
err收藏
学者 查看更多内容