咨询与建议

限定检索结果

文献类型

  • 6 篇 期刊文献

馆藏范围

  • 6 篇 电子文献
  • 0 种 纸本馆藏

日期分布

学科分类号

  • 5 篇 工学
    • 5 篇 计算机科学与技术...
    • 2 篇 软件工程
  • 3 篇 理学
    • 3 篇 数学

主题

  • 6 篇 kernelization al...
  • 2 篇 vertex cover
  • 1 篇 block graph
  • 1 篇 graph algorithms
  • 1 篇 big data
  • 1 篇 p2-packing
  • 1 篇 edge dominating ...
  • 1 篇 streaming algori...
  • 1 篇 parameterized co...
  • 1 篇 np-complete geom...
  • 1 篇 crown decomposit...
  • 1 篇 approximation al...
  • 1 篇 line cover
  • 1 篇 block decomposit...
  • 1 篇 chordal vertex d...
  • 1 篇 maximal matching
  • 1 篇 parameterized co...
  • 1 篇 fixed parameter ...

机构

  • 2 篇 texas a&m univ d...
  • 1 篇 hong kong polyte...
  • 1 篇 changsha univ sc...
  • 1 篇 eindhoven univ t...
  • 1 篇 guangzhou univ s...
  • 1 篇 depaul univ sch ...
  • 1 篇 lafayette coll d...
  • 1 篇 univ warsaw inst...
  • 1 篇 univ paris 09 la...
  • 1 篇 tech univ berlin...
  • 1 篇 cuny grad ctr ny...

作者

  • 2 篇 chen jianer
  • 1 篇 pilipczuk marcin
  • 1 篇 li wenjun
  • 1 篇 ye junjie
  • 1 篇 guo ying
  • 1 篇 cao yixin
  • 1 篇 kanj iyad
  • 1 篇 jansen bart m. p...
  • 1 篇 yang wei
  • 1 篇 kim eun jung
  • 1 篇 xia ge
  • 1 篇 kwon o-joung
  • 1 篇 chu zirui
  • 1 篇 lampis michael
  • 1 篇 huang qin

语言

  • 6 篇 英文
检索条件"主题词=kernelization algorithm"
6 条 记 录,以下是1-10 订阅
Nearly Time-Optimal kernelization algorithms for the Line-Cover Problem with Big Data
收藏 引用
algorithmICA 2024年 第8期86卷 2448-2478页
作者: Chen, Jianer Huang, Qin Kanj, Iyad Xia, Ge Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA DePaul Univ Sch Comp Chicago IL USA Lafayette Coll Dept Comp Sci Easton PA USA
Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \... 详细信息
来源: 评论
A 5k-vertex kernel for P2-packing
收藏 引用
THEORETICAL COMPUTER SCIENCE 2022年 910卷 1-13页
作者: Li, Wenjun Ye, Junjie Cao, Yixin Changsha Univ Sci & Technol Sch Comp & Commun Engn Changsha Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China
The P-2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel. (C) 20... 详细信息
来源: 评论
Space limited linear-time graph algorithms on big data
收藏 引用
THEORETICAL COMPUTER SCIENCE 2024年 993卷
作者: Chen, Jianer Chu, Zirui Guo, Ying Yang, Wei Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Guangzhou Univ Sch Comp Sci Guangzhou 510006 Peoples R China
We study algorithms for graph problems in which the graphs are of extremely large size N so that super -linear time w ( N ) or linear space Theta( N ) would become impractical. We use a parameter k to characterize the... 详细信息
来源: 评论
APPROXIMATION AND kernelization FOR CHORDAL VERTEX DELETION
收藏 引用
SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年 第3期32卷 2258-2301页
作者: Jansen, Bart M. P. Pilipczuk, Marcin Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Univ Warsaw Inst Informat PL-02097 Warsaw Poland
The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by... 详细信息
来源: 评论
A Polynomial Kernel for Block Graph Deletion
收藏 引用
algorithmICA 2017年 第1期79卷 251-270页
作者: Kim, Eun Jung Kwon, O-Joung Univ Paris 09 LAMSADE CNRS Paris France Tech Univ Berlin Log & Semant Berlin Germany
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i.... 详细信息
来源: 评论
A kernel of order 2k-c log k for vertex cover
收藏 引用
INFORMATION PROCESSING LETTERS 2011年 第23-24期111卷 1089-1091页
作者: Lampis, Michael CUNY Grad Ctr New York NY 10021 USA
In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techn... 详细信息
来源: 评论