Results 11 to 20 of about 98 (93)
Grundy Distinguishes Treewidth from Pathwidth
SIAM Journal on Discrete Mathematics, 2022 Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status ...
Rémy Belmonte +4 more
openaire +4 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.
Bodlaender, Hans, Möhring, Rolf H.
openaire +4 more sources
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant $c ...
Coudert, David +2 more
openaire +5 more sources
Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth [PDF]
ACM Journal of Experimental Algorithmics, 2016 Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest.
Coudert, David +2 more
openaire +2 more sources
Pathwidth, trees, and random embeddings [PDF]
Combinatorica, 2013 We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the ...
Lee, James R., Sidiropoulos, Anastasios
openaire +3 more sources
From Pathwidth to Connected Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2012 It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$,
openaire +5 more sources
Crossing Number for Graphs with Bounded Pathwidth [PDF]
Algorithmica, 2020 The crossing number is the smallest number of pairwise edge-crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios.
Biedl, Therese +3 more
openaire +4 more sources
The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time.
Felix Canavoi +2 more
doaj +1 more source
On edge-intersection graphs of k-bend paths in grids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2010 Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications
Therese Biedl, Michal Stern
doaj +1 more source
Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
Discrete Mathematics, 2002 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Togasaki, Mitsunori, Yamazaki, Koichi
openaire +1 more source