Results 31 to 40 of about 3,161 (171)
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
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
Tight bound on treedepth in terms of pathwidth and longest path [PDF]
Comb., 2023 We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor.
Meike Hatzel +5 more
semanticscholar +1 more source
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
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
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
The Bounded Pathwidth of Control-Flow Graphs
Proc. ACM Program. Lang., 2023 Pathwidth and treewidth are standard and well-studied graph sparsity parameters which intuitively model the degree to which a given graph resembles a path or a tree, respectively.
G. K. Conrado +2 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
First Order Logic on Pathwidth Revisited Again [PDF]
International Colloquium on Automata, Languages and Programming, 2022 Courcelle's celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each
M. Lampis
semanticscholar +1 more source