Results 41 to 50 of about 13,814 (224)
Approximating acyclicity parameters of sparse hypergraphs [PDF]
, 2008 The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity.
Fomin, Fedor V. +2 more
core +5 more sources
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path [PDF]
Symposium on the Theory of Computing, 2020 Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in O(n · 2O(τ)) time, where τ is the treewidth of the input graph.
Sally Dong, Y. Lee, Guanghao Ye
semanticscholar +1 more source
Treewidth and Hyperbolicity of the Internet [PDF]
2011 IEEE 10th International Symposium on Network Computing and Applications, 2011 We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level.
de Montgolfier, Fabien +2 more
openaire +5 more sources
Information and Computation, 2017 So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. Ordered pathwidth is roughly the same as proof space and the ordered treewidth of a proof is meant to serve as a measure of how far it is from
Moritz Müller, Stefan Szeider
openaire +2 more sources
Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting
International Conference on Principles of Knowledge Representation and Reasoning, 2021 Probabilistic reasoning, parameter learning, and most probable explanation inference for answer set programming have recently received growing attention.
Thomas Eiter +2 more
semanticscholar +1 more source
The treewidth of 2-section of hypergraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if $|f\cap g|\le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$, denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\in V([H]_2)$, $uv\in E([H]_2)$ if and only if there is $ f\in F$ such that $u,v\in f$.
Ke Liu, Mei Lu
openaire +4 more sources
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
On the treewidth of Hanoi graphs
Theoretical Computer Science, 2022 The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to ...
David Eppstein +2 more
openaire +4 more sources
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries [PDF]
, 2015 Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental problem of counting, given a conjunctive query and a relational database, the ...
Chen, Hubie, Mengel, Stefan
core +3 more sources
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 Summary: It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Hans L. Bodlaender, Rolf H. Möhring
openaire +2 more sources