全部 |
  • 全部
  • 题名
  • 作者
  • 机构
  • 关键词
  • NSTL主题词
  • 摘要
检索 二次检索 AI检索
外文文献 中文文献
筛选条件:

1. Feedback Vertex Set for Pseudo-disk Graphs in Subexponential FPT Time NSTL国家科技图书文献中心

Gaetan Berthe |  Marin Bougeret... -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 65~78 - 共14页

摘要:In this paper we investigate the existence of |  parameterized algorithms running in subexponential time for |  two fundamental cycle-hitting problems: Feedback |  Vertex Set and Triangle Hitting. We focus on the class |  of pseudo-disk graphs, which forms a common
关键词: Geometric intersection graphs |  Subexponential FPT algorithms |  Cycle-hitting problems |  Pseudo-disk graphs

2. Degreewidth on Semi-complete Digraphs NSTL国家科技图书文献中心

Ryan Keeney |  Daniel Lokshtanov -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 312~326 - 共15页

摘要:For a digraph G and ordering of G, the |  degreewidth of the ordering is the maximum number of |  backward arcs incident to any vertex of G. The |  degreewidth Δ(G) of G is defined as the minimum degreewidth |  of an ordering of G. A digraph G is semi-complete
关键词: Semi-complete digraph |  Parameterized algorithm |  Degreewidth |  Feedback arc set |  Cutwidth

3. Improved Outerplanarity Bounds for Planar Graphs NSTL国家科技图书文献中心

Therese Biedl |  Debajyoti Mondal -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 92~106 - 共15页

摘要:In this paper, we study the outerplanarity of |  planar graphs, i.e., the number of times that we must |  (in a planar embedding that we can initially freely |  choose) remove the outerface vertices until the graph |  is empty. It is well-known that there are n-vertex
关键词: Planar graphs |  Outerplanarity |  Fence girth |  Diameter

4. Recognition of Unit Segment and Polyline Graphs is {exist}R-Complete NSTL国家科技图书文献中心

Michael Hoffmann |  Tillmann Miltzow... -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 266~281 - 共16页

摘要:Given a set of objects O in the plane, the |  corresponding intersection graph is defined as follows. A |  vertex is created for each object and an edge joins two |  vertices whenever the corresponding objects intersect. We |  study here the case of unit segments and polylines
关键词: Intersection graphs |  Unit segment |  Polyline |  Recognition

5. XNLP-Hardness of Parameterized Problems on Planar Graphs NSTL国家科技图书文献中心

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. The |  class XALP consists of problems that can be solved in
关键词: Parameterized complexity |  XNLP |  XALP |  Planar graphs |  Outerplanarity

6. Approximation Algorithms for Treewidth, Pathwidth, and Treedepth - A Short Survey NSTL国家科技图书文献中心

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

7. On Polynomial Kernelization for Stable Cutset NSTL国家科技图书文献中心

Stefan Kratsch |  Van Bang Le -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 358~373 - 共16页

摘要:A stable cutset in a graph G is a set S {is |  contained in} V (G) such that vertices of S are pairwise |  non-adjacent and such that G - S is disconnected | , i.e., it is both stable (or independent) set and a |  cutset (or separator). Unlike general cutsets, it is NP
关键词: Stable cutset |  Kernelization |  Parameterized complexity

8. Graph Reconstruction with Connectivity Queries NSTL国家科技图书文献中心

Kacper Kluk |  Hoang La... -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 343~357 - 共15页

摘要:We study a problem of reconstruction of |  connected graphs where the input gives all subsets of size |  k that induce a connected subgraph. Originally |  introduced by Bastide et al. (WG 2023) for triples (k = 3 | ), this problem received comprehensive attention in
关键词: Graph reconstruction |  Triangle-free graphs |  Bounded maximum degree

9. Roman Cycle Hitting Set NSTL国家科技图书文献中心

Satyabrata Jana |  Sounak Modak... -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 282~296 - 共15页

摘要:The variant of Dominating Set known as Roman |  Domination has been extensively studied in the fields of |  graph theory and graph algorithms. Fernau and Mann |  [arXiv:2302.11417] introduced the concept of Roman |  Vertex Cover and developed a fixed-parameter tractable
关键词: Feedback vertex set |  Odd cycle transversal |  Roman hitting set |  Fixed-parameter tractability |  Kernelization

10. Enumerating Minimal Solution Sets for Metric Graph Problems NSTL国家科技图书文献中心

Benjamin Bergougnoux |  Oscar Defrain... -  《Graph-Theoretic Concepts in Computer Science》 -  International Workshop on Graph-Theoretic Concepts in Computer Science - 2025, - 50~64 - 共15页

摘要:Problems from metric graph theory like Metric |  Dimension, Geodetic Set, and Strong Metric Dimension have |  recently had a strong impact in parameterized complexity |  by being the first known problems in N P to admit |  double-exponential lower bounds in the treewidth, and
关键词: Algorithmic enumeration |  Hypergraph dualization |  Metric dimension |  Geodetic sets |  Resolving sets |  Matroids
检索条件会议:Graph-Theoretic Concepts in Computer Science
  • 检索词扩展

NSTL主题词

  • NSTL学科导航