Results 71 to 80 of about 13,679 (262)
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$.
Zongwen Bai, Jianhua Tu, Yongtang Shi
doaj +1 more source
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 MDS and Reed-Muller Codes [PDF]
, 2011 The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical ...
Kashyap, Navin, Thangaraj, Andrew
core +1 more source
A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
Algorithms, 2019 We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute.
Borislav Slavchev +2 more
doaj +1 more source
Tree-width for first order formulae [PDF]
Logical Methods in Computer Science, 2012 We introduce tree-width for first order formulae \phi, fotw(\phi). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of formulae of bounded fotw, model checking is fixed parameter tractable ...
Isolde Adler, Mark Weyer
doaj +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 +6 more sources
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
Optimizing tree decompositions in MSO [PDF]
Logical Methods in Computer Science, 2022 The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the ...
Mikołaj Bojańczyk, Michał Pilipczuk
doaj +1 more source
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
Parameterized Complexity of Equitable Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times.
Guilherme de C. M. Gomes +2 more
doaj +1 more source