Problems hard for treewidth but easy for stable gonality
From MaRDI portal
Publication:6039413
DOI10.1007/978-3-031-15914-5_7arXiv2202.06838OpenAlexW4312748023WikidataQ126176056 ScholiaQ126176056MaRDI QIDQ6039413
Marieke van der Wegen, Hans L. Bodlaender, Gunther Cornelissen
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.06838
graph algorithmsnetwork flowgraph orientationparameterized complexitytree partitionsstable gonalitycapacitated dominating set
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The structure of graphs not admitting a fixed immersion
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Complexity of secure sets
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- On tree-partition-width
- Defensive alliances in graphs of bounded treewidth
- Reduction algorithms for graphs of small treewidth
- Bin packing with fixed number of bins revisited
- Computing graph gonality is hard
- Treewidth is a lower bound on graph gonality
- A combinatorial Li-Yau inequality and rational points on curves
- On the space and circuit complexity of parameterized problems: classes and completeness
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithmic Applications of Tree-Cut Width
- Harmonic Morphisms and Hyperelliptic Graphs
- Capacitated Domination and Covering: A Parameterized Perspective
- Two-Commodity Flow
- Stable gonality is computable
- Parameterized Algorithms
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Recognizing hyperelliptic graphs in polynomial time
This page was built for publication: Problems hard for treewidth but easy for stable gonality
