Search results for "pathwidth"

Hits ?▲	Authors	Title	Venue	Year	Link
21	Therese Biedl, Markus Chimani, Martin Derka, Petra Mutzel	Crossing Number for Graphs with Bounded~Pathwidth.	ISAAC	2017	DBLP DOI BibTeX RDF
21	Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, Daniël Paulusma	Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2.	WG	2017	DBLP DOI BibTeX RDF
21	Neha Lodha, Sebastian Ordyniak, Stefan Szeider	SAT-Encodings for Special Treewidth and Pathwidth.	SAT	2017	DBLP DOI BibTeX RDF
21	Sven Mallach	Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem.	IWOCA	2017	DBLP DOI BibTeX RDF
21	Michal Pilipczuk	Computing Cutwidth and Pathwidth of Semi-complete Digraphs.	Encyclopedia of Algorithms	2016	DBLP DOI BibTeX RDF
21	Adam Gagol, Gwenaël Joret, Jakub Kozik, Piotr Micek	Pathwidth and Nonrepetitive List Coloring.	Electron. J. Comb.	2016	DBLP DOI BibTeX RDF
21	Csaba Biró, Mitchel T. Keller, Stephen J. Young	Posets with Cover Graph of Pathwidth two have Bounded Dimension.	Order	2016	DBLP DOI BibTeX RDF
21	Gregory Z. Gutin, Mark Jones 0001, Magnus Wahlström	The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth.	SIAM J. Discret. Math.	2016	DBLP DOI BibTeX RDF
21	Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano	Computing Directed Pathwidth in O(1.89n) Time.	Algorithmica	2016	DBLP DOI BibTeX RDF
21	Therese Biedl, Markus Chimani, Martin Derka, Petra Mutzel	Crossing Number for Graphs With Bounded Pathwidth.	CoRR	2016	DBLP BibTeX RDF
21	Adam Gagol, Gwenaël Joret, Jakub Kozik, Piotr Micek	Pathwidth and nonrepetitive list coloring.	CoRR	2016	DBLP BibTeX RDF
21	Yasuaki Kobayashi	Computing the pathwidth of directed graphs with small vertex cover.	Inf. Process. Lett.	2015	DBLP DOI BibTeX RDF
21	Masataka Ikeda, Hiroshi Nagamochi	Some Reduction Procedure for Computing Pathwidth of Undirected Graphs.	IEICE Trans. Inf. Syst.	2015	DBLP DOI BibTeX RDF
21	Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou 0001	The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2015	DBLP DOI BibTeX RDF
21	Keith Edwards, Eric McDermid	A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP.	Algorithmica	2015	DBLP DOI BibTeX RDF
21	Therese Biedl	Optimum-width upward drawings of trees I: Rooted pathwidth.	CoRR	2015	DBLP BibTeX RDF
21	Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki	On the pathwidth of almost semicomplete digraphs.	CoRR	2015	DBLP BibTeX RDF
21	Therese Biedl	Triangulating planar graphs while keeping the pathwidth small.	CoRR	2015	DBLP BibTeX RDF
21	Dariusz Dereniowski, Danny Dyer, Ryan M. Tifenbach, Boting Yang	Zero-visibility cops and robber and the pathwidth of a graph.	J. Comb. Optim.	2015	DBLP DOI BibTeX RDF
21	Emily Abernethy Marshall, David R. Wood	Circumference and Pathwidth of Highly Connected Graphs.	J. Graph Theory	2015	DBLP DOI BibTeX RDF
21	Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki	On the Pathwidth of Almost Semicomplete Digraphs.	ESA	2015	DBLP DOI BibTeX RDF
21	Therese Biedl	Triangulating Planar Graphs While Keeping the Pathwidth Small.	WG	2015	DBLP DOI BibTeX RDF
21	Frank Gurski, Jochen Rethmann, Egon Wanke	Directed Pathwidth and Palletizers.	COCOA	2015	DBLP DOI BibTeX RDF
21	Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad	2-Connecting outerplanar graphs without blowing up the pathwidth.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
21	Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou 0001	The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs.	CoRR	2014	DBLP BibTeX RDF
21	Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki	Outerplanar obstructions for matroid pathwidth.	Discret. Math.	2014	DBLP DOI BibTeX RDF
21	Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki	Search Space Reduction through Commitments in Pathwidth Computation: An Experimental Study.	SEA	2014	DBLP DOI BibTeX RDF
21	David Coudert, Dorian Mazauric, Nicolas Nisse	Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth.	SEA	2014	DBLP DOI BibTeX RDF
21	Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou 0001	The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs.	COCOA	2014	DBLP DOI BibTeX RDF
21	Jakub Gajarský, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar	Finite Integer Index of Pathwidth and Treewidth.	IPEC	2014	DBLP DOI BibTeX RDF
21	James R. Lee, Anastasios Sidiropoulos	Pathwidth, trees, and random embeddings.	Comb.	2013	DBLP DOI BibTeX RDF
21	Moritz Müller, Stefan Szeider	Revisiting Space in Proof Complexity: Treewidth and Pathwidth.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
21	Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger	TREEWIDTH and PATHWIDTH parameterized by vertex cover	CoRR	2013	DBLP BibTeX RDF
21	Marek Cygan	Improved approximation for 3-dimensional matching via bounded pathwidth local search	CoRR	2013	DBLP BibTeX RDF
21	Therese Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, Ignaz Rutter	Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings.	CoRR	2013	DBLP BibTeX RDF
21	Christoph Blume, H. J. Sander Bruggink, Martin Friedrich, Barbara König 0001	Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata.	J. Vis. Lang. Comput.	2013	DBLP DOI BibTeX RDF
21	Alexandra Ovetsky Fradkin, Paul D. Seymour	Tournament pathwidth and topological containment.	J. Comb. Theory, Ser. B	2013	DBLP DOI BibTeX RDF
21	Kord Eickmeyer, Ken-ichi Kawarabayashi	Approximating Multi Commodity Network Design on Graphs of Bounded Pathwidth and Bounded Degree.	SAGT	2013	DBLP DOI BibTeX RDF
21	Marek Cygan	Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search.	FOCS	2013	DBLP DOI BibTeX RDF
21	Moritz Müller, Stefan Szeider	Revisiting Space in Proof Complexity: Treewidth and Pathwidth.	MFCS	2013	DBLP DOI BibTeX RDF
21	Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger	Treewidth and Pathwidth Parameterized by the Vertex Cover Number.	WADS	2013	DBLP DOI BibTeX RDF
21	Therese Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, Ignaz Rutter	Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings.	GD	2013	DBLP DOI BibTeX RDF
21	Michal Pilipczuk	Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings.	STACS	2013	DBLP DOI BibTeX RDF
21	Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad	2-connecting Outerplanar Graphs without Blowing Up the Pathwidth.	COCOON	2013	DBLP DOI BibTeX RDF
21	Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk	An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.	Algorithmica	2012	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch	Kernel Bounds for Structural Parameterizations of Pathwidth	CoRR	2012	DBLP BibTeX RDF
21	Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad	2-connecting Outerplanar Graphs without Blowing Up the Pathwidth	CoRR	2012	DBLP BibTeX RDF
21	Michal Pilipczuk	Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings	CoRR	2012	DBLP BibTeX RDF
21	Libor Barto, Marcin Kozik, Ross Willard	Near Unanimity Constraints Have Bounded Pathwidth Duality.	LICS	2012	DBLP DOI BibTeX RDF
21	Hiroshi Nagamochi	Submodular Minimization via Pathwidth.	TAMC	2012	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender	Fixed-Parameter Tractability of Treewidth and Pathwidth.	The Multivariate Algorithmic Revolution and Beyond	2012	DBLP DOI BibTeX RDF
21	Michelangelo Grigni, Hao-Hsiang Hung	Light Spanners in Bounded Pathwidth Graphs.	MFCS	2012	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch	Kernel Bounds for Structural Parameterizations of Pathwidth.	SWAT	2012	DBLP DOI BibTeX RDF
21	Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano	Computing Directed Pathwidth in O(1.89 n ) Time.	IPEC	2012	DBLP DOI BibTeX RDF
21	Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki	Outerplanar Obstructions for Matroid Pathwidth.	Electron. Notes Discret. Math.	2011	DBLP DOI BibTeX RDF
21	Christoph Blume, H. J. Sander Bruggink, Martin Friedrich, Barbara König 0001	Treewidth, Pathwidth and Cospan Decompositions.	Electron. Commun. Eur. Assoc. Softw. Sci. Technol.	2011	DBLP DOI BibTeX RDF
21	Yota Otachi, Ryohei Suda	Bandwidth and pathwidth of three-dimensional grids	CoRR	2011	DBLP BibTeX RDF
21	Michelangelo Grigni, Hao-Hsiang Hung	Finding Light Spanners in Bounded Pathwidth Graphs	CoRR	2011	DBLP BibTeX RDF
21	Yota Otachi, Ryohei Suda	Bandwidth and pathwidth of three-dimensional grids.	Discret. Math.	2011	DBLP DOI BibTeX RDF
21	Hisao Tamaki	A Polynomial Time Algorithm for Bounded Directed Pathwidth.	WG	2011	DBLP DOI BibTeX RDF
21	Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin	CSP duality and trees of bounded pathwidth.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
21	Uffe Flarup, Laurent Lyaudet	On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth.	Theory Comput. Syst.	2010	DBLP DOI BibTeX RDF
21	Geevarghese Philip, Venkatesh Raman 0001, Yngve Villanger	A Quartic Kernel for Pathwidth-One Vertex Deletion	CoRR	2010	DBLP BibTeX RDF
21	D. Sai Krishna, T. V. Thirumala Reddy, B. Sai Shashank, C. Pandu Rangan	Pathwidth and Searching in Parameterized Threshold Graphs.	WALCOM	2010	DBLP DOI BibTeX RDF
21	Geevarghese Philip, Venkatesh Raman 0001, Yngve Villanger	A Quartic Kernel for Pathwidth-One Vertex Deletion.	WG	2010	DBLP DOI BibTeX RDF
21	Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk	An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion.	IPEC	2010	DBLP DOI BibTeX RDF
21	Joachim Kneis, Daniel Mölle, Stefan Richter 0001, Peter Rossmanith	A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms.	SIAM J. Discret. Math.	2009	DBLP DOI BibTeX RDF
21	James R. Lee, Anastasios Sidiropoulos	Pathwidth, trees, and random embeddings	CoRR	2009	DBLP BibTeX RDF
21	Frederic Dorn, Jan Arne Telle	Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
21	Navin Kashyap	Matroid Pathwidth and Code Trellis Complexity.	SIAM J. Discret. Math.	2008	DBLP DOI BibTeX RDF
21	Víctor Dalmau, Andrei A. Krokhin	Majority constraints have bounded pathwidth duality.	Eur. J. Comb.	2008	DBLP DOI BibTeX RDF
21	Uffe Flarup, Laurent Lyaudet	On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth	CoRR	2008	DBLP BibTeX RDF
21	Mugurel Ionut Andreica	A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth	CoRR	2008	DBLP BibTeX RDF
21	Boting Yang, Yi Cao	Digraph searching, directed vertex separation and directed pathwidth.	Discret. Appl. Math.	2008	DBLP DOI BibTeX RDF
21	John Ellis, Robert Warren	Lower bounds on the pathwidth of some grid-like graphs.	Discret. Appl. Math.	2008	DBLP DOI BibTeX RDF
21	Uffe Flarup, Laurent Lyaudet	On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract).	CSR	2008	DBLP DOI BibTeX RDF
21	Navin Kashyap	Matroid Pathwidth and Code Trellis Complexity	CoRR	2007	DBLP BibTeX RDF
21	Fedor V. Fomin, Dimitrios M. Thilikos	On self duality of pathwidth in polyhedral graph embeddings.	J. Graph Theory	2007	DBLP DOI BibTeX RDF
21	David Coudert, Florian Huc, Jean-Sébastien Sereni	Pathwidth of outerplanar graphs.	J. Graph Theory	2007	DBLP DOI BibTeX RDF
21	Fedor V. Fomin, Kjartan Høie	Pathwidth of cubic graphs and exact algorithms.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
21	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-approximation for the pathwidth of Halin graphs.	J. Discrete Algorithms	2006	DBLP DOI BibTeX RDF
21	L. Sunil Chandran, Telikepalli Kavitha	The treewidth and pathwidth of hypercubes.	Discret. Math.	2006	DBLP DOI BibTeX RDF
21	Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde	Embeddings of k-connected graphs of pathwidth k.	Discret. Appl. Math.	2005	DBLP DOI BibTeX RDF
21	Jan Arne Telle	Tree-decompositions of small pathwidth.	Discret. Appl. Math.	2005	DBLP DOI BibTeX RDF
21	Rodney G. Downey, Catherine McCartin	Bounded Persistence Pathwidth.	CATS	2005	DBLP BibTeX RDF
21	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-approximation for the pathwidth of Halin graphs.	Electron. Notes Discret. Math.	2004	DBLP DOI BibTeX RDF
21	Matthew Suderman	Pathwidth And Layered Drawings Of Trees.	Int. J. Comput. Geom. Appl.	2004	DBLP DOI BibTeX RDF
21	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-Approximation for the Pathwidth of Halin Graphs.	CTW	2004	DBLP BibTeX RDF
21	Janka Chlebíková	The structure of obstructions to treewidth and pathwidth.	Discret. Appl. Math.	2002	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Fedor V. Fomin	Approximation of pathwidth of outerplanar graphs.	J. Algorithms	2002	DBLP DOI BibTeX RDF
21	Jan Arne Telle	Tree-decompositions of small pathwidth.	Electron. Notes Discret. Math.	2001	DBLP DOI BibTeX RDF
21	Corinne Lucet, Jean-Francois Manouvrier, Jacques Carlier	Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs.	Algorithmica	2000	DBLP DOI BibTeX RDF
21	Janka Chlebíková	The structure of obstructions to treewidth and pathwidth.	Electron. Notes Discret. Math.	1999	DBLP DOI BibTeX RDF
21	Rajeev Govindan, Michael A. Langston, Xudong Yan	Approximation the Pathwidth of Outerplanar Graphs.	Inf. Process. Lett.	1998	DBLP DOI BibTeX RDF
21	Fedor V. Fomin	Helicopter Search Problems, Bandwidth and Pathwidth.	Discret. Appl. Math.	1998	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Ton Kloks	Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs.	J. Algorithms	1996	DBLP DOI BibTeX RDF
21	Haim Kaplan, Ron Shamir	Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques.	SIAM J. Comput.	1996	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Ton Kloks, Dieter Kratsch	Treewidth and Pathwidth of Permutation Graphs.	SIAM J. Discret. Math.	1995	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks	Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree.	J. Algorithms	1995	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Rolf H. Möhring	The Pathwidth and Treewidth of Cographs.	SIAM J. Discret. Math.	1993	DBLP DOI BibTeX RDF