Hans L. Bodlaender -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 3～18 - 共16页

摘要：This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.

关键词： Treewidth |  Pathwidth |  Treedepth |  Approximation |  Graph algorithms

Hans L. Bodlaender |  Krisztina Szilagyi -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 107～120 - 共14页

摘要：The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)n~(O(1)) time and g(k) log n space, where n is the size of the input instance and k the parameter. Th...

关键词： Parameterized complexity |  XNLP |  XALP |  Planar graphs |  Outerplanarity

Hans L. Bodlaender |  Matthew Johnson... -  《Combinatorial Algorithms: 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings》 -  International Workshop on Combinatorial Algorithms - 2024, - 206～217 - 共12页

摘要：We study Steiner Forest on H-subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. We are motivated by a recent framework that completel...

关键词： Steiner forest |  Forbidden subgraph |  Complexity dichotomy |  Vertex cover number |  Deletion set

Hans L. Bodlaender |  Lars Jaffke... -  《Theory of computing systems》 - 2023,67(1) - 52～88 - 共37页

摘要：Abstract In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain construc...

关键词： Typical sequences |  Treewidth |  Series parallel digraphs |  Cutwidth |  Modified cutwidth

Hans L. Bodlaender |  Carla Groenland... -  《IEEE 62nd Annual Symposium on Foundations of Computer Science: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 7-10 Feb. 2022, Virtual Conference, Denver, CO, USA》 -  IEEE Annual Symposium on Foundations of Computer Science - 2022, - 193～204 - 共12页

摘要：Let XNLP be the class of parameterized prob-lems such that an instance of size $n$ with parameter...

关键词： Computer science |  Processor scheduling |  Bandwidth |  Complexity theory

Hans L. Bodlaender |  Gunther Cornelissen... -  《Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tubingen, Germany, June 22-24, 2022, Revised Selected Papers》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2022, - 84～97 - 共14页

摘要：We show that some natural problems that are XNLP -hard (hence W[t]-hard for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph paramet...

关键词： Parameterized complexity |  Graph algorithms |  Network flow |  Graph orientation |  Capacitated dominating set |  Tree partitions |  Stable gonality

Hans L. Bodlaender -  《Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2021, - 15～27 - 共13页

摘要：In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t ∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path...

关键词： Bandwidth |  Parameterized complexity |  Weighted path emulation |  W-hierarchy |  Caterpillars

NSTL主题词： Caterpillar |  Bandwidth |  simulating |  parameterization

Toshiki Saitoh |  Ryo Yoshinaka... -  《WALCOM: Algorithms and Computation: 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), February 28 – March 2, 2021, Yangon, Myanmar》 -  International Conference and Workshops on Algorithms and Computation - 2021, - 142～153 - 共12页

摘要：For a graph class C, the C-EDGE-DELETION problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C-EDGE-DELETION problem for C the c...

关键词： Parameterized algorithms |  Treewidth |  Edge-Deletion |  Interval graphs

NSTL主题词： efficient algorithm |  algorithms |  Classes

Hans L. Bodlaender |  Hirotaka Ono... -  《International Conference on Autonomous Agents and Multiagent Systems: AAMAS 2020, Online, 9-13 May 2020, volume 3 of 3》 -  International Conference on Autonomous Agents and Multiagent Systems - 2021, - 1760～1762 - 共3页

摘要：In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on...

关键词： Hedonic game |  Stability |  Envy-freeness |  Computational complexity |  Parameterized complexity |  Local search

NSTL主题词： seat |  Lexical permutation sorting

Hans L. Bodlaender |  Benjamin Burton... -  《Graph-theoretic concepts in computer science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2020, - 80～91 - 共12页

摘要：In this paper, we study knot diagrams for which the underlying graph has treewidth two. We give a linear time algorithm for the following problem: given a knot diagram of treewidth two, does it repres...

关键词： Knot diagrams |  Knot theory |  Graph algorithms |  Treewidth |  Series parallel graphs

NSTL主题词： Knot Theory |  Nautical mile per hour |  Knots