Results 251 to 260 of about 14,736 (264)
Some of the next articles are maybe not open access.
Treewidth Inapproximability and Tight ETH Lower Bound
Symposium on the Theory of ComputingDespite the (algorithmic) importance of treewidth, both its complexity and approximability present large knowledge gaps. While the best currently known polynomial-time approximation algorithm has ratio O(√logOPT), no approximation factor could be ruled ...
Édouard Bonnet
semanticscholar +1 more source
Faster Sampling Algorithms for Polytopes with Small Treewidth
BigData Congress [Services Society]Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities.
Yekun Ke +3 more
semanticscholar +1 more source
Excluding a Clique or a Biclique in Graphs of Bounded Induced Matching Treewidth
SIAM Journal on Discrete MathematicsFor a tree decomposition $\mathcal{T}$ of a graph $G$, let $\mu(\mathcal{T})$ denote the maximum size of an induced matching in $G$ with the property that some bag of $\mathcal{T}$ contains at least one endpoint of every edge of the matching. The induced
Tara Abrishami +6 more
semanticscholar +1 more source
Sparse Induced Subgraphs of Large Treewidth
J. Comb. Theory BMotivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Seymour [JCTB '86] or by a classic result of Chekuri and Chuzhoy [SODA '15 ...
Édouard Bonnet
semanticscholar +1 more source
2014
• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs.
openaire +5 more sources
• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs.
openaire +5 more sources
Treewidth of Circular-Arc Graphs
SIAM Journal on Discrete Mathematics, 1994It is shown that the treewidth of circular-arc graphs and the corresponding tree-decomposition can be found in \(O(n^ 3)\) time. Let \(G= (V,E)\) be a circular-arc graph corresponding to a family \(\{A_ 0, A_ 1,\dots, A_{n-1}\}\) of arcs on a unit circle. Define a left clique \(S_ i\) by \(S_ i= \{A_ j\mid A_ j\) contains the left end points of \(A_ i\}
Sundaram, Ravi +2 more
openaire +2 more sources
Approximation Algorithms for Treewidth
Algorithmica, 2008zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
Treewidth and Pure Nash Equilibria
2013We consider the complexity of w-PNE-GG, the problem of computing pure Nash equilibria in graphical games parameterized by the treewidth w of the underlying graph. It is well-known that the problem of computing pure Nash equilibria is NP-hard in general, but in polynomial time when restricted to games of bounded treewidth.
Thomas, A., van Leeuwen, J.
openaire +2 more sources