Zobrazeno 1 - 10
of 223
pro vyhledávání: '"Hans L. Bodlaender"'
Autor:
Hans L. Bodlaender
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol 3, Iss 4 (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 fa
Externí odkaz:
https://doaj.org/article/ecd7174528974df793e27398638e6ce7
Publikováno v:
European Journal of Combinatorics. 66:191-234
One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theore
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::055315ab5b407cdf8303fa2ad5510019
https://doi.org/10.1016/j.ejc.2017.06.025
https://doi.org/10.1016/j.ejc.2017.06.025
This book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017.The 31 full papers presented in this volume were carefully
Publikováno v:
SIAM Journal on Discrete Mathematics, 28(1), 277-305. Society for Industrial and Applied Mathematics (SIAM)
We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded para
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bafe9f056c540129a67a8d019db0f03a
https://doi.org/10.1137/120880240
https://doi.org/10.1137/120880240
Autor:
Hans L. Bodlaender, Jurriaan Hage
Publikováno v:
Theoretical Computer Science. 429:30-35
In this paper we consider a connection between switching (of undirected graphs), and the notions of NLC-width, cliquewidth and treewidth. In particular, we show that the NLC-widths and the cliquewidths of two graphs in a switching class are at most a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d0bec75e9611e73898c33be6ef3c810d
https://doi.org/10.1016/j.tcs.2011.12.021
https://doi.org/10.1016/j.tcs.2011.12.021
Publikováno v:
Discrete Applied Mathematics. 159:2147-2164
The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Se
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6ec1e10491193de331a8a831f630c84d
https://doi.org/10.1016/j.dam.2011.07.001
https://doi.org/10.1016/j.dam.2011.07.001
Publikováno v:
Discrete Mathematics. 311:1040-1045
In 1987, Simonson conjectured that every k-outerplanar graph of maximum degree d has spanning tree congestion at most [email protected]?d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20 (1987) 235-252]. We s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7dd512208260dc0ece606dad1d8ae213
https://doi.org/10.1016/j.disc.2011.03.002
https://doi.org/10.1016/j.disc.2011.03.002
Publikováno v:
Journal of Scheduling, 15(3), 323-332. Springer
We investigate a class of scheduling problems that arise in the optimization of SQL queries for parallel machines (Chekuri et al. in PODS'95, pp. 255---265, 1995). In these problems, an undirected graph is used to represent communication and inter-op
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e6547fa4478a69c4ea57d19998dfdb15
https://doi.org/10.1007/s10951-011-0225-1
https://doi.org/10.1007/s10951-011-0225-1
Publikováno v:
Algorithmica. 61:817-838
We present two parameterized algorithms for the Minimum Fill-in problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time $\mat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::649af7cb97ad2b9adef3798bcab8f612
https://doi.org/10.1007/s00453-010-9421-1
https://doi.org/10.1007/s00453-010-9421-1
Publikováno v:
Information and Computation. 208:259-275
For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast.This paper gives an overview of several upper bound heuristics that have been proposed
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b85818aae3605d7188e59a1a18e9a11d
https://doi.org/10.1016/j.ic.2009.03.008
https://doi.org/10.1016/j.ic.2009.03.008