On tradeoffs between width- and fill-like graph parameters
From MaRDI portal
Publication:1999998
DOI10.1007/s00224-018-9882-1zbMath1414.05155arXiv1802.09620OpenAlexW2789139888MaRDI QIDQ1999998
Adam Stański, Dariusz Dereniowski
Publication date: 27 June 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.09620
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Distance in graphs (05C12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On minimum cost edge searching
- The complexity of minimum-length path decompositions
- The complexity of subgraph isomorphism for classes of partial k-trees
- Connected graph searching
- An annotated bibliography on guaranteed graph searching
- Interval graphs and searching
- Black-white pebbles and graph separation
- The vertex separation number of a graph equals its path-width
- On the pathwidth of chordal graphs
- Graph searching and a min-max theorem for tree-width
- Treewidth. Computations and approximations
- Fugitive-search games on graphs and related parameters
- Graph searching, elimination trees, and a generalization of bandwidth
- Tree decompositions with small cost
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Searching and pebbling
- Graph Searching and Interval Completion
- Tridiagonalization by permutations
- Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
- Connected Treewidth and Connected Graph Searching
- On interval graphs and matrice profiles
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- Complete Register Allocation Problems
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- From Pathwidth to Connected Pathwidth
- Recontamination does not help to search a graph
- Minimum size tree-decompositions
