Results 81 to 90 of about 11,104 (228)
Optimal Padded Decomposition For Bounded Treewidth Graphs [PDF]
TheoretiCSA $(β,δ,Δ)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $Δ$ such that for every vertex $v\in V$, the probability that $\rm{ball}_G(v,γΔ)$ is entirely contained in the ...
Arnold Filtser +6 more
doaj +1 more source
Counting Linear Extensions: Parameterizations by Treewidth. [PDF]
Algorithmica, 2019 We consider the # P -complete problem of counting the number of linear extensions of a poset ( # LE ) ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of # LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations ...
Eiben E, Ganian R, Kangas K, Ordyniak S.
europepmc +9 more sources
, 2018 We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $G=(V,E)$, find a shortest walk ("route") from a source $s\in V$ to a destination $t\in V$ that includes all vertices specified by a set $\mathscr{W}\subseteq V$: the
Amiri, Saeed Akhoondian +2 more
core +1 more source
, 2005 Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a tree decomposition of small width. Both theoretical results, establishing the asymptotic computational complexity of the problem, as experimental work on ...
openaire +3 more sources
The treewidth of smart contracts [PDF]
Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, 2019 Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money in the form of cryptocurrency units. Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars ...
Chatterjee, Krishnendu +2 more
openaire +2 more sources
Structural properties of graph products
Journal of Graph Theory, Volume 109, Issue 2, Page 107-136, June 2025.Abstract Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this result, this paper systematically studies various structural properties of cartesian, direct and strong products.
Robert Hickingbotham, David R. Wood
wiley +1 more source
Diameter and Treewidth in Minor-Closed Graph Families
, 1999 It is known that any planar graph with diameter D has treewidth O(D), and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families.
Eppstein, David
core +2 more sources
On Constrained Minimum Weight Edge Covers With Applications to Emergency Planning
Networks, Volume 85, Issue 3, Page 261-271, April 2025.ABSTRACT In this paper we present a new covering problem, called Min Cost q$$ q $$‐Single Location Cover, where we are given a fixed positive integer q$$ q $$, a finite ground set J$$ J $$, an integral positive demand dj$$ {d}_j $$ for each element j∈J$$ j\in J $$, a collection 𝒥 of subsets of J$$ J $$, an integral positive cost cS$$ {c}_S $$ and an ...
Shai Dimant, Sven O. Krumke
wiley +1 more source
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bodlaender, H.L., Koster, A.M.C.A.
openaire +5 more sources
Bidimensional Parameters and Local Treewidth [PDF]
SIAM Journal on Discrete Mathematics, 2004 Summary: For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by \(k\), then the treewidth of the graph is bounded by some function of \(k\). This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs ...
Demaine, Erik D. +3 more
openaire +2 more sources