The Library
Linear time algorithm for computing a small biclique in graphs without long induced paths
Tools
Atminas, Aistis, Lozin, Vadim V. and Razgon, Igor (2012) Linear time algorithm for computing a small biclique in graphs without long induced paths. In: Algorithm Theory – SWAT 2012. Algorithm Theory – SWAT 2012 Book Subtitle 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, Vol.7357 . London : Springer, pp. 142-152.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-31155-0_13
Abstract
The biclique problem asks, given a graph G and a parameter k, whether G has a complete bipartite subgraph of k vertices in each part (a biclique of order k). Fixed-parameter tractability of this problem is a longstanding open question in parameterized complexity that received a lot of attention from the community. In this paper we consider a restricted version of this problem by introducing an additional parameter s and assuming that G does not have induced (i.e. chordless) paths of length s. We prove that under this parameterization the problem becomes fixed-parameter linear. The main tool in our proof is a Ramsey-type theorem stating that a graph with a long (not necessarily induced) path contains either a long induced path or a large biclique.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Series Name: | Algorithm Theory – SWAT 2012 Book Subtitle 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings | ||||
Publisher: | Springer | ||||
Place of Publication: | London | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithm Theory – SWAT 2012 | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Vol.7357 | ||||
Page Range: | pp. 142-152 | ||||
DOI: | 10.1007/978-3-642-31155-0_13 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Description: | Algorithm Theory – SWAT 2012 : 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |