Exploring the gap between treedepth and vertex cover through vertex integrity
From MaRDI portal
Publication:5925679
DOI10.1007/978-3-030-75242-2_19OpenAlexW3164438458MaRDI QIDQ5925679
Masashi Kiyomi, Tatsuya Gima, Yasuaki Kobayashi, Tesshu Hanaka, Yota Otachi
Publication date: 22 March 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_19
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The parameterised complexity of list problems on graphs of bounded treewidth
- Sparsity. Graphs, structures, and algorithms
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- On the complexity of some colorful problems parameterized by treewidth
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- On the computational complexity of vertex integrity and component order connectivity
- The Steiner forest problem revisited
- Balanced vertex-orderings of graphs
- Parameterized complexity of length-bounded cuts and multicuts
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- Bin packing with fixed number of bins revisited
- On structural parameterizations of the bounded-degree vertex deletion problem
- The graph motif problem parameterized by the structure of the input graph
- Imbalance is fixed parameter tractable
- Maximum common induced subgraph parameterized by vertex cover
- Monadic second order logic on graphs with local cardinality constraints
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Integer Programming with a Fixed Number of Variables
- Easy problems for tree-decomposable graphs
- Capacitated Domination and Covering: A Parameterized Perspective
- Graph Layout Problems Parameterized by Vertex Cover
- What Makes Equitable Connected Partition Easy
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- New Results on Directed Edge Dominating Set
- Metric Dimension of Bounded Tree-length Graphs
- Parameterized Algorithms
- Imbalance parameterized by twin cover revisited
- Subgraph isomorphism on graph classes that exclude a substructure
- Parameterized Complexity of Geodetic Set
This page was built for publication: Exploring the gap between treedepth and vertex cover through vertex integrity
