咨询与建议

限定检索结果

文献类型

  • 8 篇 期刊文献
  • 2 篇 会议

馆藏范围

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

日期分布

学科分类号

  • 8 篇 工学
    • 6 篇 计算机科学与技术...
    • 2 篇 软件工程
    • 1 篇 控制科学与工程
  • 7 篇 理学
    • 7 篇 数学

主题

  • 10 篇 exact exponentia...
  • 2 篇 3-disjoint conne...
  • 2 篇 np hard problems
  • 2 篇 graph algorithms
  • 2 篇 enumerating conn...
  • 2 篇 minimum maximal ...
  • 2 篇 k-weighted verte...
  • 2 篇 parameterized al...
  • 2 篇 treewidth
  • 2 篇 path contraction
  • 2 篇 #minimum dominat...
  • 2 篇 #3-coloring
  • 1 篇 graphs
  • 1 篇 maximum satisfia...
  • 1 篇 -regular subgrap...
  • 1 篇 coloring
  • 1 篇 space-efficient ...
  • 1 篇 counting
  • 1 篇 combinatorial up...
  • 1 篇 algorithms

机构

  • 2 篇 inst math sci ch...
  • 2 篇 it univ copenhag...
  • 2 篇 univ bergen dept...
  • 1 篇 mit comp sci & a...
  • 1 篇 nyu ny 10003 usa
  • 1 篇 weizmann inst sc...
  • 1 篇 univ paul verlai...
  • 1 篇 eindhoven univ t...
  • 1 篇 university of ca...
  • 1 篇 univ bergen pob ...
  • 1 篇 institute of mat...
  • 1 篇 institute of mat...
  • 1 篇 univ calif santa...
  • 1 篇 univ bergen dept...
  • 1 篇 ben-gurion unive...
  • 1 篇 hbni inst math s...
  • 1 篇 univ durham sch ...
  • 1 篇 univ orleans lab...
  • 1 篇 university of be...
  • 1 篇 hbni inst math s...

作者

  • 5 篇 saurabh saket
  • 5 篇 fomin fedor v.
  • 3 篇 lokshtanov danie...
  • 2 篇 tale prafullkuma...
  • 2 篇 agrawal akanksha
  • 2 篇 kutzkov konstant...
  • 2 篇 gaspers serge
  • 2 篇 stepanov alexey ...
  • 1 篇 golovnev alexand...
  • 1 篇 vyas nikhil
  • 1 篇 kratsch dieter
  • 1 篇 venkatesh raman
  • 1 篇 bansal nikhil
  • 1 篇 pyatkin artem
  • 1 篇 golovach petr a.
  • 1 篇 chitnis rajesh
  • 1 篇 liedloff mathieu
  • 1 篇 nederlof jesper
  • 1 篇 ramanujan m. s.
  • 1 篇 sushmita gupta

语言

  • 10 篇 英文
检索条件"主题词=Exact exponential time algorithms"
10 条 记 录,以下是1-10 订阅
排序:
An exact exponential time algorithm for counting bipartite cliques
收藏 引用
INFORMATION PROCESSING LETTERS 2012年 第13期112卷 535-539页
作者: Kutzkov, Konstantin IT Univ Copenhagen Copenhagen Denmark
We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n vertices. We achieve running time of O(1.2491(n)), improving upon known exact algorithms for finding and counting bipa... 详细信息
来源: 评论
New exact algorithms for the 2-constraint satisfaction problem
收藏 引用
THEORETICAL COMPUTER SCIENCE 2014年 526卷 18-27页
作者: Golovnev, Alexander Kutzkov, Konstantin NYU New York NY 10003 USA IT Univ Copenhagen Copenhagen Denmark
Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. algorithms solving the problem e... 详细信息
来源: 评论
Faster exact algorithms for some terminal set problems
收藏 引用
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 88卷 195-207页
作者: Chitnis, Rajesh Fomin, Fedor V. Lokshtanov, Daniel Misra, Pranabendu Ramanujan, M. S. Saurabh, Saket Weizmann Inst Sci Fac Math & Comp Sci Rehovot Israel Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India
Many problems on graphs can be expressed in the following language: given a graph G = (V, E) and a terminal set T subset of V, find a minimum size set S subset of V which intersects all "structures" (such as... 详细信息
来源: 评论
PATH CONTRACTION FASTER THAN 2n
收藏 引用
SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年 第2期34卷 1302-1325页
作者: Agrawal, Akanksha Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Tale, Prafullkumar Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Bergen POB 7800 N-5020 Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA HBNI Inst Math Sci Chennai 600113 Tamil Nadu India UMI ReLax Chennai Tamil Nadu India
A graph G is contractible to a graph H if there is a set X subset of E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs the F-CONTR... 详细信息
来源: 评论
Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
收藏 引用
THEORY OF COMPUTING SYSTEMS 2013年 第4期52卷 645-667页
作者: Couturier, Jean-Francois Golovach, Petr A. Kratsch, Dieter Liedloff, Mathieu Pyatkin, Artem Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France
Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs... 详细信息
来源: 评论
FASTER SPACE-EFFICIENT algorithms FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS
收藏 引用
SIAM JOURNAL ON COMPUTING 2018年 第5期47卷 1755-1777页
作者: Bansal, Nikhil Garg, Shashwat Nederlof, Jesper Vyas, Nikhil Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 AB Eindhoven Netherlands MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA
We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assumin... 详细信息
来源: 评论
On Two Techniques of Combining Branching and Treewidth
收藏 引用
ALGORITHMICA 2009年 第2期54卷 181-207页
作者: Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India
Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In ... 详细信息
来源: 评论
On Two Techniques of Combining Branching and Treewidth
On Two Techniques of Combining Branching and Treewidth
收藏 引用
17th International Symposium on algorithms and Computation (ISAAC 2006)
作者: Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India
Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In ... 详细信息
来源: 评论
Path contraction faster than 2n  46
Path contraction faster than 2n
收藏 引用
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
作者: Agrawal, Akanksha Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Tale, Prafullkumar Ben-Gurion University of the Negev Beersheba Israel University of Bergen Bergen Norway University of California Santa Barbara Santa BarbaraCA United States Institute of Mathematical Sciences HBNI and UMI ReLaX Chennai India Institute of Mathematical Sciences HBNI Chennai India
A graph G is contractible to a graph H if there is a set X ⊆ E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contractio... 详细信息
来源: 评论
Maximum
收藏 引用
SIAM Journal on Discrete Mathematics 2012年 第4期26卷 1758-1780页
作者: Sushmita Gupta Venkatesh Raman Saket Saurabh
We show that for a fixed rrr, the number of maximal r