Search

Your search keyword '"Pathwidth"' showing total 3 results
Start Over Descriptor "Pathwidth" Search Limiters Full Text Publisher association for computing machinery
3 results on '"Pathwidth"'

1. Solving Problems on Recursively Constructed Graphs.

Author

BORIE, RICHARD B., PARKER, R. GARY, and TOVEY, CRAIG A.

Subjects
*COMPUTER algorithms, *RECURSIVE functions, *COMPUTER programming, *GRAPH theory, *DYNAMIC programming, *GRAPH coloring
Abstract

Fast algorithms can be created for many graph problems when instances are confined to classes of graphs that are recursively constructed. This article first describes some basic conceptual notions regarding the design of such fast algorithms, and then the coverage proceeds through several recursive graph classes. Specific classes include trees, series-parallel graphs, k-terminal graphs, treewidth-k graphs, k-trees, partial k-trees, k-jackknife graphs, pathwidth-k graphs, bandwidth-k graphs, cutwidth-k graphs, branchwidth-k graphs, Halin graphs, cographs, cliquewidth-k graphs, k-NLC graphs, k-HB graphs, and rankwidth-k graphs. The definition of each class is provided. Typical algorithms are applied to solve problems on instances of most classes. Relationships between the classes are also discussed. [ABSTRACT FROM AUTHOR]

Published
2008
Full Text
View/download PDF

2. Parametrised complexity of satisfiability in temporal logic

Author

Lück, Martin, Meier, Arne, Schindler, Irena, Lück, Martin, Meier, Arne, and Schindler, Irena

Abstract

We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle's famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. By investigating Boolean operator fragments in the sense of Post's lattice, we achieve the same complexity as in the unrestricted case if the set of available Boolean functions can express the function "negation of the implication." Conversely, we show containment in FPT for almost all other clones. © ACM 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic 18 (2017), Nr. 1, 1. DOI: https://doi.org/10.1145/3001835.

Published
2017

3. Parametrised complexity of satisfiability in temporal logic

Author

Arne Meier, Irena Schindler, and Martin Lück

Subjects
Tree-width, General Computer Science, Logic, Boolean circuit, Treewidth, Pathwidth, Temporal logic, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Complexity, Formal logic, 01 natural sciences, Theoretical Computer Science, Combinatorics, Linear temporal logic, 0202 electrical engineering, electronic engineering, information engineering, ddc:510, Boolean functions, Computer Science::Data Structures and Algorithms, Boolean function, Mathematics, Discrete mathematics, Parametrised complexity, Second-order logic, Temporal depth, Multimodal logic, Post's lattice, Computation tree logic, Computer circuits, Dewey Decimal Classification::500 | Naturwissenschaften::510 | Mathematik, Computational Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Boolean satisfiability problem
Abstract

We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle's famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. By investigating Boolean operator fragments in the sense of Post's lattice, we achieve the same complexity as in the unrestricted case if the set of available Boolean functions can express the function "negation of the implication." Conversely, we show containment in FPT for almost all other clones. © ACM 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic 18 (2017), Nr. 1, 1. DOI: https://doi.org/10.1145/3001835. DFG/ME 4279/1-1

Published
2017

Catalog

Books, media, physical & digital resources
See catalog results