Results 1 to 10 of about 745 (85)
Separating layered treewidth and row treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems.
Prosenjit Bose +4 more
doaj +1 more source
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source
Classes of graphs with restricted interval models [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a
Andrzej Proskurowski, Jan Arne Telle
doaj +3 more sources
A new two-variable generalization of the chromatic polynomial [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph.
Klaus Dohmen +2 more
doaj +3 more sources
Recent Advances in Positive-Instance Driven Graph Searching
Algorithms, 2022 Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017).
Max Bannach, Sebastian Berndt
doaj +1 more source
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1 [PDF]
International Workshop on Graph-Theoretic Concepts in Computer Science, 2023 Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1.
Jakob Baumann +2 more
semanticscholar +1 more source
On Approximating Cutwidth and Pathwidth [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2023 We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized.
Nikhil Bansal +2 more
semanticscholar +1 more source
Pathwidth Versus Cocircumference [PDF]
SIAM Journal on Discrete Mathematics, 2023 The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel\'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper
Marcin Brianski, G. Joret, M. Seweryn
semanticscholar +1 more source
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that
Bogdan Alecu +5 more
semanticscholar +1 more source
2-Layer Graph Drawings with Bounded Pathwidth [PDF]
J. Graph Algorithms Appl., 2022 We determine which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
D. Wood
semanticscholar +1 more source