Results 51 to 60 of about 4,776 (247)
The Treewidth of Induced Graphs of Conditional Preference Networks Is Small
Information, 2016 Conditional preference networks (CP-nets) are recently an emerging topic as a graphical model for compactly representing ordinal conditional preference relations on multi-attribute domains.
Jie Liu, Jinglei Liu
doaj +1 more source
Tuza's Conjecture for Threshold Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including
Marthe Bonamy +6 more
doaj +1 more source
Explainable activity recognition in videos: Lessons learned
Applied AI Letters, Volume 2, Issue 4, December 2021., 2021 Abstract We consider the following activity recognition task: given a video, infer the set of activities being performed in the video and assign each frame to an activity. This task can be solved using modern deep learning architectures based on neural networks or conventional classifiers such as linear models and decision trees.
Chiradeep Roy +7 more
wiley +1 more source
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Algorithms, 2021 Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been ...
Johannes K. Fichte +3 more
doaj +1 more source
Tractable Abstract Argumentation via Backdoor-Treewidth
AAAI Conference on Artificial Intelligence, 2022 Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to ...
Wolfgang Dvořák +5 more
semanticscholar +1 more source
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2021 In this article, we present Approximation Schemes for Capacitated Vehicle Routing Problem (CVRP) on several classes of graphs. In CVRP, introduced by Dantzig and Ramser in 1959 [14], we are given a graph G=(V,E) with metric edges costs, a depot r ∈ V ...
Aditya Jayaprakash, M. Salavatipour
semanticscholar +1 more source
Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
Journal of Graph Theory, Volume 98, Issue 1, Page 81-109, September 2021., 2021 Abstract We continue research into a well‐studied family of problems that ask whether the vertices of a given graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We consider the case where G is the class of k‐degenerate graphs.
Marthe Bonamy +4 more
wiley +1 more source
Clan embeddings into trees, and low treewidth graphs [PDF]
Symposium on the Theory of Computing, 2021 In low distortion metric embeddings, the goal is to embed a host “hard” metric space into a “simpler” target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric.
Arnold Filtser, Hung Le
semanticscholar +1 more source
A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
Algorithms, 2019 We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute.
Borislav Slavchev +2 more
doaj +1 more source
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path [PDF]
Symposium on the Theory of Computing, 2020 Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in O(n · 2O(τ)) time, where τ is the treewidth of the input graph.
Sally Dong, Y. Lee, Guanghao Ye
semanticscholar +1 more source