Results 81 to 90 of about 13,679 (262)
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source
On Treewidth, Separators and Yao’s Garbling [PDF]
, 2021 We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size \(S\) and treewidth \(w\) with only a \({S^{O({w})}}\) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss.
Kamath Hosdurg, Chethan +2 more
openaire +2 more sources
Decomposition-Guided Reductions for Argumentation and Treewidth
International Joint Conference on Artificial Intelligence, 2021 Argumentation is a widely applied framework for modeling and evaluating arguments and its reasoning with various applications. Popular frameworks are abstract argumentation (Dung’s framework) or logic-based argumentation (Besnard-Hunter’s framework ...
J. Fichte +3 more
semanticscholar +1 more source
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2020 Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour.
Vincent Cohen-Addad +3 more
semanticscholar +1 more source
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity [PDF]
, 2015 Kernelization is a theoretical formalization of efficient preprocessing for NP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-the-art ILP-solvers like CPLEX.
A. Atamtürk +7 more
core +2 more sources
Practical Access to Dynamic Programming on Tree Decompositions
Algorithms, 2019 Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood.
Max Bannach, Sebastian Berndt
doaj +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
Cycle decompositions of pathwidth‐6 graphs
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +1 more source
Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Algorithms, 2019 Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science.
Robert Ganian, Sebastian Ordyniak
doaj +1 more source
On Interval Routing Schemes and treewidth [PDF]
Information and Computation, 1995 AbstractIn this paper, we investigate which processor networks allowk-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixedk⩾1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This
Hans L. Bodlaender +5 more
openaire +4 more sources