Results 1 to 10 of about 282 (94)
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
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 Path-Width of Integer Linear Programming [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it.
Constantin Enea +3 more
doaj +1 more source
Constrained Connectivity in Bounded X-Width Multi-Interface Networks
Algorithms, 2020 As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere.
Alessandro Aloisio, Alfredo Navarra
doaj +1 more source
Linear Datalog and Bounded Path Duality of Relational Structures [PDF]
Logical Methods in Computer Science, 2005 In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs.
Victor Dalmau
doaj +1 more source
Cycle decompositions of pathwidth‐6 graphs
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +1 more source