Results 31 to 40 of about 2,730 (147)
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM Transactions on Algorithms, 2022 We describe a polynomial-time algorithm which, given a graphGwith treewidtht, approximates the pathwidth ofGto within a ratio of\(O(t\sqrt {\log t})\). This is the first algorithm to achieve anf(t)-approximation for some functionf.Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a ...
Carla Groenland +3 more
openalex +8 more sources
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
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
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
The structure of obstructions to treewidth and pathwidth
Electronic Notes in Discrete Mathematics, 2002 AbstractIt is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w⩽3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp.
Janka Chlebı́ková
openalex +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 +4 more sources
The treewidth and pathwidth of graph unions
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 the answer is no even if $G_1$ is a binary tree and $G_2$ is a ternary tree.
Bogdan Alecu +5 more
openalex +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