Search results for "pathwidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Treewidth, Graph searching, Pathwidth
3	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	MFCS	2005	DBLP DOI BibTeX RDF	treewidth, graph searching, pathwidth
2	Rodica Mihai, Ioan Todinca	Pathwidth is NP-Hard for Weighted Trees.	FAW	2009	DBLP DOI BibTeX RDF
2	Karol Suchan, Yngve Villanger	Computing Pathwidth Faster Than 2n.	IWPEC	2009	DBLP DOI BibTeX RDF
2	Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar, David R. Wood	Improved upper bounds on the crossing number.	Symposium on Computational Geometry	2008	DBLP DOI BibTeX RDF	convex crossing number, rectilinear crossing number, graph drawing, treewidth, crossing number, graph minors, pathwidth, maximum degree
2	Richard B. Borie, R. Gary Parker, Craig A. Tovey	Solving problems on recursively constructed graphs.	ACM Comput. Surv.	2008	DBLP DOI BibTeX RDF	Halin graph, branchwidth, cliquewidth, cutwidth, rankwidth, series parallel, dynamic programming, tree, Bandwidth, treewidth, cograph, pathwidth
2	David Coudert, Florian Huc, Dorian Mazauric	Computing and Updating the Process Number in Trees.	OPODIS	2008	DBLP DOI BibTeX RDF	process number, distributed algorithm, Pathwidth
2	Boting Yang	Strong-mixed searching and pathwidth.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Node search, Edge search, Mixed search, Cops-and-robber game, Pursuit-evasion problem
2	Karol Suchan, Ioan Todinca	Pathwidth of Circular-Arc Graphs.	WG	2007	DBLP DOI BibTeX RDF
2	Sheng-Lung Peng, Yi-Chuan Yang	On the Treewidth and Pathwidth of Biconvex Bipartite Graphs.	TAMC	2007	DBLP DOI BibTeX RDF
2	Pierre Fraigniaud, Nicolas Nisse	Monotony Properties of Connected Visible Graph Searching.	WG	2006	DBLP DOI BibTeX RDF	Treewidth, Graph Searching, Pathwidth
2	Rodney G. Downey, Catherine McCartin	Online Problems, Pathwidth, and Persistence.	IWPEC	2004	DBLP DOI BibTeX RDF
2	Fedor V. Fomin	Pathwidth of Planar and Line Graphs.	Graphs and Combinatorics	2003	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender	Necessary Edges in k-Chordalisations of Graphs.	J. Comb. Optim.	2003	DBLP DOI BibTeX RDF	triangulated graphs, graph algorithms, interval graphs, treewidth, chordal graphs, pathwidth
2	Fedor V. Fomin, Hans L. Bodlaender	Approximation of Pathwidth of Outerplanar Graphs.	WG	2001	DBLP DOI BibTeX RDF
2	Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde	Embeddings of k-Connected Graphs of Pathwidth k.	SWAT	2000	DBLP DOI BibTeX RDF
2	Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos	Isomorphism for Graphs of Bounded Distance Width.	Algorithmica	1999	DBLP DOI BibTeX RDF	Distance pathwidth, Distance treewidth, Graph isomorphism, Fixed parameter tractability
2	Hans L. Bodlaender, Ton Kloks, Dieter Kratsch	Treewidth and Pathwidth of Permutation Graphs.	ICALP	1993	DBLP DOI BibTeX RDF
2	Ton Kloks, Hans L. Bodlaender	Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, John R. Gilbert, Ton Kloks, Hjálmtyr Hafsteinsson	Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height.	WG	1991	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Ton Kloks	Better Algorithms for the Pathwidth and Treewidth of Graphs.	ICALP	1991	DBLP DOI BibTeX RDF
2	Hans L. Bodlaender, Rolf H. Möhring	The Pathwidth and Treewidth of Cographs.	SWAT	1990	DBLP DOI BibTeX RDF
1	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
1	Hiroshi Nagamochi	Submodular Minimization via Pathwidth.	TAMC	2012	DBLP DOI BibTeX RDF
1	Christoph Blume, Harrie Jan Sander Bruggink, Martin Friedrich, Barbara König	Treewidth, Pathwidth and Cospan Decompositions.	ECEASST	2011	DBLP BibTeX RDF
1	Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki	Outerplanar Obstructions for Matroid Pathwidth.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Yota Otachi, Ryohei Suda	Bandwidth and pathwidth of three-dimensional grids.	Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Yota Otachi, Ryohei Suda	Bandwidth and pathwidth of three-dimensional grids	CoRR	2011	DBLP BibTeX RDF
1	Michelangelo Grigni, Hao-Hsiang Hung	Finding Light Spanners in Bounded Pathwidth Graphs	CoRR	2011	DBLP BibTeX RDF
1	Hisao Tamaki	A Polynomial Time Algorithm for Bounded Directed Pathwidth.	WG	2011	DBLP DOI BibTeX RDF
1	Dariusz Dereniowski	From Pathwidth to Connected Pathwidth.	STACS	2011	DBLP DOI BibTeX RDF
1	Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin	CSP duality and trees of bounded pathwidth.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Dariusz Dereniowski	From Pathwidth to Connected Pathwidth	CoRR	2010	DBLP BibTeX RDF
1	Geevarghese Philip, Venkatesh Raman, Yngve Villanger	A Quartic Kernel for Pathwidth-One Vertex Deletion	CoRR	2010	DBLP BibTeX RDF
1	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
1	Geevarghese Philip, Venkatesh Raman, Yngve Villanger	A Quartic Kernel for Pathwidth-One Vertex Deletion.	WG	2010	DBLP DOI BibTeX RDF
1	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
1	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
1	James R. Lee, Anastasios Sidiropoulos	Pathwidth, trees, and random embeddings	CoRR	2009	DBLP BibTeX RDF
1	Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith	A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms.	SIAM J. Discrete Math.	2009	DBLP DOI BibTeX RDF
1	Frederic Dorn, Jan Arne Telle	Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm.	Discrete Applied Mathematics	2009	DBLP DOI BibTeX RDF
1	Rosa Enciso, Michael R. Fellows, Jiong Guo, Iyad A. Kanj, Frances A. Rosamond, Ondrej Suchý	What Makes Equitable Connected Partition Easy.	IWPEC	2009	DBLP DOI BibTeX RDF
1	Michael R. Fellows, Jiong Guo, Iyad A. Kanj	The Parameterized Complexity of Some Minimum Label Problems.	WG	2009	DBLP DOI BibTeX RDF
1	Víctor Dalmau, Andrei A. Krokhin	Majority constraints have bounded pathwidth duality.	Eur. J. Comb.	2008	DBLP DOI BibTeX RDF
1	Mugurel Ionut Andreica	A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth	CoRR	2008	DBLP BibTeX RDF
1	Uffe Flarup, Laurent Lyaudet	On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth	CoRR	2008	DBLP BibTeX RDF
1	Navin Kashyap	Matroid Pathwidth and Code Trellis Complexity.	SIAM J. Discrete Math.	2008	DBLP DOI BibTeX RDF
1	Boting Yang, Yi Cao	Digraph searching, directed vertex separation and directed pathwidth.	Discrete Applied Mathematics	2008	DBLP DOI BibTeX RDF
1	John Ellis, Robert Warren	Lower bounds on the pathwidth of some grid-like graphs.	Discrete Applied Mathematics	2008	DBLP DOI BibTeX RDF
1	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
1	Robert Mateescu, Rina Dechter	AND/OR Multi-valued Decision Diagrams for Constraint Networks.	Concurrency, Graphs and Models	2008	DBLP DOI BibTeX RDF
1	Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose	Dualities for Constraint Satisfaction Problems.	Complexity of Constraints	2008	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin	On Problems without Polynomial Kernels (Extended Abstract).	ICALP	2008	DBLP DOI BibTeX RDF
1	Michael Lampis, Georgia Kaouri, Valia Mitsou	On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures.	ISAAC	2008	DBLP DOI BibTeX RDF	Digraph decompositions, Treewidth, Parameterized Complexity
1	Md. Jawaherul Alam, Md. Abul Hassan Samee, Mashfiqui Rabbi, Md. Saidur Rahman	Upward Drawings of Trees on the Minimum Number of Layers.	WALCOM	2008	DBLP DOI BibTeX RDF	Planar Drawing, k-layer Planar Drawing, Upward Drawing, Minimum Layer Upward Drawing, Algorithm, Trees, Line-labeling, Straight-line Drawing
1	David Coudert, Florian Huc, Dorian Mazauric	A Distributed Algorithm for Computing and Updating the Process Number of a Forest.	DISC	2008	DBLP DOI BibTeX RDF
1	Vida Dujmovic, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Sue Whitesides, David R. Wood	On the Parameterized Complexity of Layered Graph Drawing.	Algorithmica	2008	DBLP DOI BibTeX RDF
1	Navin Kashyap	Matroid Pathwidth and Code Trellis Complexity	CoRR	2007	DBLP BibTeX RDF
1	Fedor V. Fomin, Dimitrios M. Thilikos	On self duality of pathwidth in polyhedral graph embeddings.	Journal of Graph Theory	2007	DBLP DOI BibTeX RDF
1	David Coudert, Florian Huc, Jean-Sébastien Sereni	Pathwidth of outerplanar graphs.	Journal of Graph Theory	2007	DBLP DOI BibTeX RDF
1	Navin Kashyap	The "Art of Trellis Decoding" Is NP-Hard.	AAECC	2007	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Saket Saurabh	Improved Exact Algorithms for Counting 3- and 4-Colorings.	COCOON	2007	DBLP DOI BibTeX RDF
1	Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh	Better Algorithms and Bounds for Directed Maximum Leaf Problems.	FSTTCS	2007	DBLP DOI BibTeX RDF
1	Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger	Characterizing Minimal Interval Completions.	STACS	2007	DBLP DOI BibTeX RDF
1	David Richerby, Dimitrios M. Thilikos	Graph Searching in a Crime Wave.	WG	2007	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Kjartan Høie	Pathwidth of cubic graphs and exact algorithms.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
1	L. Sunil Chandran, Telikepalli Kavitha	The treewidth and pathwidth of hypercubes.	Discrete Mathematics	2006	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-approximation for the pathwidth of Halin graphs.	J. Discrete Algorithms	2006	DBLP DOI BibTeX RDF
1	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Clique-width minimization is NP-hard.	STOC	2006	DBLP DOI BibTeX RDF	absolute approximation, NP-completeness, clique-width, pathwidth
1	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Nash equilibria in graphical games on trees revisited.	ACM Conference on Electronic Commerce	2006	DBLP DOI BibTeX RDF	PPAD-completeness, nash equilibrium, graphical games
1	Robert Mateescu, Rina Dechter	Compiling Constraint Networks into AND/OR Multi-valued Decision Diagrams (AOMDDs).	CP	2006	DBLP DOI BibTeX RDF
1	Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde	Embeddings of k-connected graphs of pathwidth k.	Discrete Applied Mathematics	2005	DBLP DOI BibTeX RDF
1	Jan Arne Telle	Tree-decompositions of small pathwidth.	Discrete Applied Mathematics	2005	DBLP DOI BibTeX RDF
1	Rodney G. Downey, Catherine McCartin	Bounded Persistence Pathwidth.	CATS	2005	DBLP BibTeX RDF
1	Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith	Algorithms Based on the Treewidth of Sparse Graphs.	WG	2005	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-approximation for the pathwidth of Halin graphs.	Electronic Notes in Discrete Mathematics	2004	DBLP DOI BibTeX RDF
1	Matthew Suderman	Pathwidth And Layered Drawings Of Trees.	Int. J. Comput. Geometry Appl.	2004	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Dimitrios M. Thilikos	A 3-Approximation for the Pathwidth of Halin Graphs.	CTW	2004	DBLP BibTeX RDF
1	Jinbo Huang, Adnan Darwiche	Using DPLL for Efficient OBDD Construction.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle	Graph Searching, Elimination Trees, and a Generalization of Bandwidth.	Algorithmica	2004	DBLP DOI BibTeX RDF	Bandwidth, Chordal graph, Graph searching, Tree decomposition, Elimination tree
1	L. Sunil Chandran, Telikepalli Kavitha, C. R. Subramanian	Isoperimetric Inequalities and the Width Parameters of Graphs.	COCOON	2003	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle	Graph Searching, Elimination Trees, and a Generalization of Bandwidth.	FCT	2003	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos	Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms.	MFCS	2003	DBLP DOI BibTeX RDF
1	Mitsunori Togasaki, Koichi Yamazaki	Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs.	Discrete Mathematics	2002	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Fedor V. Fomin	Approximation of pathwidth of outerplanar graphs.	J. Algorithms	2002	DBLP DOI BibTeX RDF
1	Janka Chlebíková	The structure of obstructions to treewidth and pathwidth.	Discrete Applied Mathematics	2002	DBLP DOI BibTeX RDF
1	Claudson F. Bornstein, Santosh Vempala	Flow Metrics.	LATIN	2002	DBLP DOI BibTeX RDF
1	Jan Arne Telle	Tree-decompositions of small pathwidth.	Electronic Notes in Discrete Mathematics	2001	DBLP DOI BibTeX RDF
1	Vida Dujmovic, Michael R. Fellows, Michael T. Hallett, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Matthew Suderman, Sue Whitesides, David R. Wood	On the Parameterized Complexity of Layered Graph Drawing.	ESA	2001	DBLP DOI BibTeX RDF
1	Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender	A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.	ESA	2001	DBLP DOI BibTeX RDF
1	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
1	Janka Chlebíková	The structure of obstructions to treewidth and pathwidth.	Electronic Notes in Discrete Mathematics	1999	DBLP DOI BibTeX RDF
1	Rajeev Govindan, Michael A. Langston, Xudong Yan	Approximation the Pathwidth of Outerplanar Graphs.	Inf. Process. Lett.	1998	DBLP DOI BibTeX RDF
1	Fedor V. Fomin	Helicopter Search Problems, Bandwidth and Pathwidth.	Discrete Applied Mathematics	1998	DBLP DOI BibTeX RDF
1	Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle	Memory Requirements for Table Computations in Partial k-tree Algorithms.	SWAT	1998	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Petr A. Golovach	Interval Completion with the Smallest Max-degree.	WG	1998	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Ton Kloks	Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs.	J. Algorithms	1996	DBLP DOI BibTeX RDF
1	Haim Kaplan, Ron Shamir	Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques.	SIAM J. Comput.	1996	DBLP DOI BibTeX RDF
1	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
1	Hans L. Bodlaender, Ton Kloks, Dieter Kratsch	Treewidth and Pathwidth of Permutation Graphs.	SIAM J. Discrete Math.	1995	DBLP DOI BibTeX RDF