Results 51 to 60 of about 13,814 (224)
On $r$-Guarding Thin Orthogonal Polygons [PDF]
, 2016 Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point $p$ to guard a point $q$ if ...
Biedl, Therese, Mehrabi, Saeed
core +2 more sources
On Interval Routing Schemes and treewidth [PDF]
Information and Computation, 1995 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hans L. Bodlaender +5 more
openaire +4 more sources
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
Journal of Combinatorial Theory, Series B, 2018 The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph $G$ is equivalent to determining the minimum vertex congestion of an embedding of $G$ into a tree.
Daniel J. Harvey, David R. Wood
openaire +3 more sources
Treewidth and pathwidth of permutation graphs [PDF]
SIAM Journal on Discrete Mathematics, 1993 This paper is the first one in a series of articles using scanlines in intersection models of graphs. The new concept enables to prove that every minimal triangulation of a permutation graph into a chordal graph is an interval graph, a result that generalizes to minimal triangulations of asteroidal-triple free graphs [Discrete Appl. Math.
Ton Kloks +2 more
openaire +5 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 Exploring Temporal Graphs of Small Pathwidth [PDF]
, 2018 We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is ...
Bodlaender, Hans L. +1 more
core +2 more sources
On Low Treewidth Graphs and Supertrees [PDF]
Journal of Graph Algorithms and Applications, 2014 Compatibility of unrooted phylogenetic trees is a well studied problem in phylogenetics. It asks to determine whether for a set of k input trees T1,...,Tk there exists a larger tree (called a supertree) that contains the topologies of all k input trees. When any such supertree exists we call the instance compatible and otherwise incompatible.
Alexander Grigoriev +2 more
openaire +5 more sources
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
A note on domino treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c_k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c_k,d. This note gives a new simple proof of this fact, with a better bound for c_k,d, namely (9k+7)d(d+1) -1. It is also shown that a lower bound of Ω (kd)
openaire +8 more sources