Results 31 to 40 of about 13,814 (224)
Clique‐width: Harnessing the power of atoms
Journal of Graph Theory, Volume 104, Issue 4, Page 769-810, December 2023., 2023 Abstract Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class G ${\mathscr{G}}$ if they are so on the atoms (graphs with no clique cut‐set) of G ${\mathscr{G}}$.
Konrad K. Dabrowski +4 more
wiley +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
The treewidth of smart contracts [PDF]
Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, 2019 Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money in the form of cryptocurrency units. Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars ...
Chatterjee, Krishnendu +2 more
openaire +3 more sources
Vertex covering with capacitated trees
Networks, Volume 81, Issue 2, Page 253-277, March 2023., 2023 Abstract The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs.
Ralf Borndörfer +2 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
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs [PDF]
, 2010 The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99].
Das, Bireswar +2 more
core +5 more sources
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
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
Are there any good digraph width measures? [PDF]
, 2010 Several different measures for digraph width have appeared in the last few years. However, none of them shares all the "nice" properties of treewidth: First, being \emph{algorithmically useful} i.e.
B. Courcelle +15 more
core +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