Fetching the paper…
Reading the bibliography…
We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem.
W. T. Tutte, The factorization of linear graphs, J. London Math. Soc
1947
Earlier work this paper cites.
H. Robbins, A remark on Stirling’s formula, Amer. Math. Monthly
1955
Earlier work this paper cites.
J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B
1967
Earlier work this paper cites.
R. A. DeMillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Inform. Process Lett
1978
Earlier work this paper cites.
P. Hell and D. Kirkpatrick, On the complexity of a generalized matching problem, in Proc. 10th ACM Symposium on Theory of Computing, STOC (San Diego, CA, USA, May 1–3, 1978), pages 309–318, 1978
1978
Earlier work this paper cites.
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach
1980
Earlier work this paper cites.
I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10(4):713–717, 1981
1981
Earlier work this paper cites.
I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10:718–720, 1981
1981
Earlier work this paper cites.
D. Leven and Z. Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithm. 4(1):35–44, 1983
1983
Earlier work this paper cites.
B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics
1985
Earlier work this paper cites.
H. L. Bodlaender, On linear time minor tests with depth-first search, J. Algorithm. 14(1):1–23, 1993
1993
Earlier work this paper cites.
N. Alon, R. Yuster, and U. Zwick, Color-coding, J. Assoc. Comput. Mach
1995
Earlier work this paper cites.
C. Papadimitriou and M. Yannakakis, On limited non- determinism and the complexity of the V-C dimension, J. Comput. Syst. Sci. 53:161–170, 1996
1996
Cited alongside, same era.
R. G. Downey and M. R. Fellows, Parameterized Complexity , Springer, 1999
1999
Cited alongside, same era.
R. Impagliazzo, R. Paturi, F. Zane, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci. 63:512–530, 2001
2001
Cited alongside, same era.
M. R. Fellows, P. Heggernes, F. A. Rosamond, C. Sloper, and J. A. Telle, Exact algorithms for finding k k disjoint triangles in an arbitrary graph, in Proc. 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 (Bad Honnef, Germany, June 21–23, 2004), Springer LNCS 3353, pages 257–269, 2004
2004
Cited alongside, same era.
W. Jia, C. Zhang, and J. Chen, An efficient parameterized algorithm for m m -set packing, J. Algorithm. 50(1):106–117, 2004
I. Koutis, Faster algebraic algorithms for path and packing problems, in Proc. 35th International Colloquium on Automata, Languages and Programming, ICALP (Reykjavik, Iceland, July 7–11, 2008), Springer LNCS 5125, pages 575–586, 2008
2008
Later among the works it cites.
Ł. Kowalik, Edge colouring, in F. Fomin et al. (eds.), Open Problems: Moderately Exponential Time Algorithms , Dagstuhl Seminar Proceedings 08431, 2008
2008
Later among the works it cites.
J. Wang and Q. Feng, An O ∗ ( 3.523 k ) O^{*}(3.523^{k}) parameterized algorithm for 3-set packing, in Proc. 5th International Conference on Theory and Applications of Models of Computation, TAMC (Xi’an, China, April 25–29, 2008), Springer LNCS 4978, pages 82–93, 2008
2008
Later among the works it cites.
J. Wang, D. Ning, Q. Feng, and J. Chen, Improved parameterized algorithm for P 2 P_{2} -packing problem (in Chinese), Journal of Software 19(11):2879–2886, 2008
2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2004
Cited alongside, same era.
L. Mathieson, E. Prieto, and P. Shaw, Packing edge disjoint triangles: a parameterized view, in Proc. 1st International Workshop on Parameterized and Exact Computation, IWPEC (Bergen, Norway, September 14–17, 2004) Springer LNCS 3162, pages 127–137, 2004
2004
Cited alongside, same era.
I. Koutis, A faster parameterized algorithm for set packing, Inform. Process Lett. 94:7–9, 2005
2005
Cited alongside, same era.
J. Kneis, D. Mölle, S. Richter, and P. Rossmanith, Divide-and-color, in Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG (Bergen, Norway, June 22–24, 2006), Springer LNCS 4271, pages 58–67, 2006
2006
Cited alongside, same era.
Y. Liu, S. Lu, J. Chen, and S.-H. Sze, Greedy localization and color-coding: improved matching and packing algorithms, in Proc. 2nd International Workshop on Parameterized and Exact Computation, IWPEC (Zürich, Switzerland, September 13-15, 2006), Springer LNCS 4169, pages 84–95, 2006
2006
Cited alongside, same era.
E. Prieto and C. Sloper, Looking at the stars, Theor. Comp. Sc
2006
Cited alongside, same era.
J. Chen, S. Lu, S.-H. Sze, and F. Zhang, Improved algorithms for path, matching, and packing problems, in Proc. 18th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2007 (Philadelphia, PA, USA, 2007), pages 298–307
2007
Cited alongside, same era.
M. R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. M. Thilikos, S. Whitesides, Faster fixed-parameter tractable algorithms for matching and packing problems, Algorithmica 52(2):167–176, 2008
2008
Cited alongside, same era.
A. Björklund, T. Husfeldt, and M. Koivisto, Set partitioning via inclusion–exclusion. SIAM J. Comput 39(2):546–563, 2009
2009
Later among the works it cites.
H. Fernau and D. Raible, A parameterized perspective on packing paths of length two, J. Comb. Optim. 18(4):319–341, 2009
2009
Later among the works it cites.
I. Koutis and R. Williams, Limits and applications of group algebras for parameterized problems, in Proc. 36th International Colloquium on Automata, Languages and Programming, ICALP (Rhodes, Greece, July 5–12, 2009), Springer LNCS 5555, pages 653–664, 2009
2009
Later among the works it cites.
Ł. Kowalik, Improved edge-coloring with three colors, Theor. Comput. Sci. 410(38–40):3733–3742, 2009
2009
Later among the works it cites.
2009
Later among the works it cites.
A. Björklund, Exact covers via determinants, in Proc. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 (Nancy, France, March 4–6, 2010), LIPIcs 5 Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pages 95–106, 2010
2010
Closest in time.
A. Björklund, Determinant sums for undirected Hamiltonicity, in Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010 (Las Vegas, USA, October 23–26, 2010)
2010
Closest in time.
P. Golovac, D. Kratsch, and J.-F. Couturier, Colorings with few colors: Counting, enumeration and combinatorial bounds, in Proc. 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG (Zaros, Crete, Greece, June 28–30, 2010)
2010
Closest in time.