Results 1 to 10 of about 65 (63)
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
Two Results on Layered Pathwidth and Linear Layouts
Journal of Graph Algorithms and Applications, 2021 Layered pathwidth is a new graph parameter studied by Bannister et al. (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is
Vida Dujmović, Pat Morin, Céline Yelle
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
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
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
2-Layer Graph Drawings with Bounded Pathwidth
Journal of Graph Algorithms and Applications, 2023 This paper determines which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
David Wood
doaj +1 more source
Order Reconfiguration under Width Constraints
Journal of Graph Algorithms and Applications, 2023 In this work, we consider the following order reconfiguration problem: Given a graph $G$ together with linear orders $\omega$ and $\omega'$ of the vertices of $G$, can one transform $\omega$ into $\omega'$ by a sequence of swaps of adjacent elements in ...
Emmanuel Arrighi +3 more
doaj +1 more source
Effect of Steaming as Postprocessing Method on Rice Flour and Jaggery 3D Printed Construct
Journal of Food Quality, Volume 2022, Issue 1, 2022., 2022 In this study, the 3D printing of a traditional South Indian snack, “sweet pidikollukattai” has been attempted. The mixing properties of the rice flour used and thermal characteristics of the paste (rice flour, jaggery, and water) have been reported. The traditional form of the product (control) was compared with the 3D printed product, which has been ...
S. Thangalakshmi +7 more
wiley +1 more source
On the Pathwidth of Hyperbolic 3-Manifolds
Computing in Geometry and Topology, 2022 According to Mostow's celebrated rigidity theorem, the geometry of closed hyperbolic 3-manifolds is already determined by their topology. In particular, the volume of such manifolds is a topological invariant and, as such, has been subject of ...
Kristóf Huszár
doaj +1 more source