Results 51 to 60 of about 13,679 (262)
On the Treewidth of Dynamic Graphs [PDF]
Theoretical Computer Science, 2013 Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability.
Bernard Mans, Luke Mathieson
openaire +4 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
Model counting for CNF formuals of bounded module treewidth. [PDF]
, 2013 The modular treewidth of a graph is its treewidth after the contraction of modules. Modular treewidth properly generalizes treewidth and is itself properly generalized by clique-width.
Paulusma, Daniel +2 more
core +4 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
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity [PDF]
Logical Methods in Computer Science, 2019 This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity.
Dušan Knop +3 more
doaj +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
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
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