Search results for "pathwidth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
110	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	MFCS	2005	DBLP DOI BibTeX RDF	treewidth, graph searching, pathwidth
101	Fedor V. Fomin	Pathwidth of Planar and Line Graphs.	Graphs Comb.	2003	DBLP DOI BibTeX RDF
101	Hans L. Bodlaender, Ton Kloks, Dieter Kratsch	Treewidth and Pathwidth of Permutation Graphs.	ICALP	1993	DBLP DOI BibTeX RDF
101	Ton Kloks, Hans L. Bodlaender	Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
94	Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse	Nondeterministic Graph Searching: From Pathwidth to Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Treewidth, Graph searching, Pathwidth
85	Fedor V. Fomin, Hans L. Bodlaender	Approximation of Pathwidth of Outerplanar Graphs.	WG	2001	DBLP DOI BibTeX RDF
69	Karol Suchan, Ioan Todinca	Pathwidth of Circular-Arc Graphs.	WG	2007	DBLP DOI BibTeX RDF
69	Hans L. Bodlaender, Ton Kloks	Better Algorithms for the Pathwidth and Treewidth of Graphs.	ICALP	1991	DBLP DOI BibTeX RDF
64	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
57	Pierre Fraigniaud, Nicolas Nisse	Monotony Properties of Connected Visible Graph Searching.	WG	2006	DBLP DOI BibTeX RDF	Treewidth, Graph Searching, Pathwidth
57	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
53	Rodica Mihai, Ioan Todinca	Pathwidth is NP-Hard for Weighted Trees.	FAW	2009	DBLP DOI BibTeX RDF
53	Karol Suchan, Yngve Villanger	Computing Pathwidth Faster Than 2n.	IWPEC	2009	DBLP DOI BibTeX RDF
53	Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde	Embeddings of k-Connected Graphs of Pathwidth k.	SWAT	2000	DBLP DOI BibTeX RDF
53	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
53	Hans L. Bodlaender, Rolf H. Möhring	The Pathwidth and Treewidth of Cographs.	SWAT	1990	DBLP DOI BibTeX RDF
48	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Nash equilibria in graphical games on trees revisited.	EC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, nash equilibrium, graphical games
41	David Coudert, Dorian Mazauric, Nicolas Nisse	Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth.	ACM J. Exp. Algorithmics	2016	DBLP DOI BibTeX RDF
41	Dariusz Dereniowski	From Pathwidth to Connected Pathwidth.	SIAM J. Discret. Math.	2012	DBLP DOI BibTeX RDF
41	Dariusz Dereniowski	From Pathwidth to Connected Pathwidth.	STACS	2011	DBLP DOI BibTeX RDF
41	Dariusz Dereniowski	From Pathwidth to Connected Pathwidth	CoRR	2010	DBLP BibTeX RDF
41	Mitsunori Togasaki, Koichi Yamazaki	Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs.	Discret. Math.	2002	DBLP DOI BibTeX RDF
41	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
41	Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar, David R. Wood	Improved upper bounds on the crossing number.	SCG	2008	DBLP DOI BibTeX RDF	convex crossing number, rectilinear crossing number, graph drawing, treewidth, crossing number, graph minors, pathwidth, maximum degree
41	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
41	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
37	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
37	Sheng-Lung Peng, Yi-Chuan Yang	On the Treewidth and Pathwidth of Biconvex Bipartite Graphs.	TAMC	2007	DBLP DOI BibTeX RDF
37	Rodney G. Downey, Catherine McCartin	Online Problems, Pathwidth, and Persistence.	IWPEC	2004	DBLP DOI BibTeX RDF
32	L. Sunil Chandran, Telikepalli Kavitha, C. R. Subramanian 0001	Isoperimetric Inequalities and the Width Parameters of Graphs.	COCOON	2003	DBLP DOI BibTeX RDF
32	Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle	Memory Requirements for Table Computations in Partial k-tree Algorithms.	SWAT	1998	DBLP DOI BibTeX RDF
32	Siddharthan Ramachandramurthi	A Lower Bound for Treewidth and Its Consequences.	WG	1994	DBLP DOI BibTeX RDF
32	Michael R. Fellows, Michael T. Hallett, Harold T. Wareham	DNA Physical Mapping: Three Ways Difficult.	ESA	1993	DBLP DOI BibTeX RDF
25	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
25	Hans L. Bodlaender	A linear time algorithm for finding tree-decompositions of small treewidth.	STOC	1993	DBLP DOI BibTeX RDF	graph algorithms, treewidth, graph minors, pathwidth, partial k-trees
21	Marcin Brianski, Gwenaël Joret, Michal T. Seweryn	Pathwidth Versus Cocircumference.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
21	Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich 0001, Igor Razgon, Viktor Zamaraev	The Treewidth and Pathwidth of Graph Unions.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
21	Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak	Tight Bound on Treedepth in Terms of Pathwidth and Longest Path.	Comb.	2024	DBLP DOI BibTeX RDF
21	Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Mark Siggers, Siani Smith	Graph Homomorphism, Monotone Classes and Bounded Pathwidth.	CoRR	2024	DBLP DOI BibTeX RDF
21	Michael Lampis	The Primal Pathwidth SETH.	CoRR	2024	DBLP DOI BibTeX RDF
21	Patrizio Angelini, Giordano Da Lozzo, Henry Förster, Thomas Schneck	2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth.	Comput. J.	2024	DBLP DOI BibTeX RDF
21	Alessandro Aloisio, Alfredo Navarra	On Coverage in Multi-Interface Networks with Bounded Pathwidth.	AINA (6)	2024	DBLP DOI BibTeX RDF
21	Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Chun Kit Lam	The Bounded Pathwidth of Control-Flow Graphs.	Proc. ACM Program. Lang.	2023	DBLP DOI BibTeX RDF
21	Sergey Norin, Alex Scott 0001, David R. Wood	Clustered colouring of graph classes with bounded treedepth or pathwidth.	Comb. Probab. Comput.	2023	DBLP DOI BibTeX RDF
21	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating Pathwidth for Graphs of Small Treewidth.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
21	David R. Wood	2-Layer Graph Drawings with Bounded Pathwidth.	J. Graph Algorithms Appl.	2023	DBLP DOI BibTeX RDF
21	Nikhil Bansal 0001, Dor Katzelnick, Roy Schwartz 0002	Almost Logarithmic Approximation for Cutwidth and Pathwidth.	CoRR	2023	DBLP DOI BibTeX RDF
21	Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak	Tight bound on treedepth in terms of pathwidth and longest path.	CoRR	2023	DBLP DOI BibTeX RDF
21	Jakob Baumann, Matthias Pfretzschner, Ignaz Rutter	Parameterized Complexity of Vertex Splitting to Pathwidth at most 1.	CoRR	2023	DBLP DOI BibTeX RDF
21	Marcin Brianski, Gwenaël Joret, Michal T. Seweryn	Pathwidth vs cocircumference.	CoRR	2023	DBLP DOI BibTeX RDF
21	Shoji Kasahara, Jun Kawahara, Shin-ichi Minato, Jumpei Mori	DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks.	IEICE Trans. Inf. Syst.	2023	DBLP DOI BibTeX RDF
21	Michael Lampis	First Order Logic on Pathwidth Revisited Again.	ICALP	2023	DBLP DOI BibTeX RDF
21	Jakob Baumann, Matthias Pfretzschner, Ignaz Rutter	Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1.	WG	2023	DBLP DOI BibTeX RDF
21	Therese Biedl	Horton-Strahler number, rooted pathwidth and upward drawings of trees.	Inf. Process. Lett.	2022	DBLP DOI BibTeX RDF
21	Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi	Grundy Distinguishes Treewidth from Pathwidth.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
21	Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos	A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
21	Dekel Tsur	Faster algorithm for pathwidth one vertex deletion.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
21	Louis Dublois, Michael Lampis, Vangelis Th. Paschos	Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
21	Michael Lampis	First Order Logic on Pathwidth Revisited Again.	CoRR	2022	DBLP DOI BibTeX RDF
21	David R. Wood	2-Layer Graph Drawings with Bounded Pathwidth.	CoRR	2022	DBLP DOI BibTeX RDF
21	Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich 0001, Igor Razgon, Viktor Zamaraev	The treewidth and pathwidth of graph unions.	CoRR	2022	DBLP BibTeX RDF
21	Lars Jaffke, Paloma T. Lima, Roohani Sharma	b-Coloring Parameterized by Pathwidth is XNLP-complete.	CoRR	2022	DBLP DOI BibTeX RDF
21	Kristóf Huszár	On the Pathwidth of Hyperbolic 3-Manifolds.	Comput. Geom. Topol.	2022	DBLP BibTeX RDF
21	Vida Dujmovic, Pat Morin, Céline Yelle	Two Results on Layered Pathwidth and Linear Layouts.	J. Graph Algorithms Appl.	2021	DBLP DOI BibTeX RDF
21	Yunlong Liu 0001, Jie Chen 0072, Jingui Huang, Jianxin Wang 0001	On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
21	Louis Dublois, Michael Lampis, Vangelis Th. Paschos	Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation.	CoRR	2021	DBLP BibTeX RDF
21	Kristóf Huszár	On the pathwidth of hyperbolic 3-manifolds.	CoRR	2021	DBLP BibTeX RDF
21	Martin E. Dyer, Catherine S. Greenhill, Haiko Müller	Counting independent sets in graphs with bounded bipartite pathwidth.	Random Struct. Algorithms	2021	DBLP DOI BibTeX RDF
21	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating Pathwidth for Graphs of Small Treewidth.	SODA	2021	DBLP DOI BibTeX RDF
21	Louis Dublois, Michael Lampis, Vangelis Th. Paschos	Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximation.	CIAC	2021	DBLP DOI BibTeX RDF
21	Vida Dujmovic, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood	Minor-Closed Graph Classes with Bounded Layered Pathwidth.	SIAM J. Discret. Math.	2020	DBLP DOI BibTeX RDF
21	Tony Huynh, Gwenaël Joret, Piotr Micek, David R. Wood	Seymour's Conjecture on 2-Connected Graphs of Large Pathwidth.	Comb.	2020	DBLP DOI BibTeX RDF
21	Therese Biedl, Markus Chimani, Martin Derka, Petra Mutzel	Crossing Number for Graphs with Bounded Pathwidth.	Algorithmica	2020	DBLP DOI BibTeX RDF
21	Patrizio Angelini, Giordano Da Lozzo, Henry Förster, Thomas Schneck	2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth.	CoRR	2020	DBLP BibTeX RDF
21	Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi	Grundy Distinguishes Treewidth from Pathwidth.	CoRR	2020	DBLP BibTeX RDF
21	Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos	A linear fixed parameter tractable algorithm for connected pathwidth.	CoRR	2020	DBLP BibTeX RDF
21	Vida Dujmovic, Pat Morin, Céline Yelle	Two Results on Layered Pathwidth and Linear Layouts.	CoRR	2020	DBLP BibTeX RDF
21	Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak	Approximating pathwidth for graphs of small treewidth.	CoRR	2020	DBLP BibTeX RDF
21	Christine T. Cheng, Will Rosenbaum	Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth.	CoRR	2020	DBLP BibTeX RDF
21	Elke Fuchs, Laura Gellert, Irene Heinrich	Cycle decompositions of pathwidth-6 graphs.	J. Graph Theory	2020	DBLP DOI BibTeX RDF
21	Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos	A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth.	ESA	2020	DBLP DOI BibTeX RDF
21	Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi	Grundy Distinguishes Treewidth from Pathwidth.	ESA	2020	DBLP DOI BibTeX RDF
21	Patrizio Angelini, Giordano Da Lozzo, Henry Förster, Thomas Schneck	2-Layer k-Planar Graphs - Density, Crossing Lemma, Relationships, and Pathwidth.	GD	2020	DBLP DOI BibTeX RDF
21	Yunlong Liu 0001, Jie Chen 0072, Jingui Huang, Jianxin Wang 0001	On Fixed-Order Book Thickness Parameterized by the Pathwidth of the Vertex Ordering.	AAIM	2020	DBLP DOI BibTeX RDF
21	Hans L. Bodlaender, Tom C. van der Zanden	On exploring always-connected temporal graphs of small pathwidth.	Inf. Process. Lett.	2019	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.	Algorithmica	2019	DBLP DOI BibTeX RDF
21	Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid	Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.	CoRR	2019	DBLP BibTeX RDF
21	Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid	Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.	ICALP	2019	DBLP DOI BibTeX RDF
21	Martin E. Dyer, Catherine S. Greenhill, Haiko Müller	Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth.	WG	2019	DBLP DOI BibTeX RDF
21	Sven Mallach	Linear ordering based MIP formulations for the vertex separation or pathwidth problem.	J. Discrete Algorithms	2018	DBLP DOI BibTeX RDF
21	Tony Huynh, Gwenaël Joret, Piotr Micek, David R. Wood	Seymour's conjecture on 2-connected graphs of large pathwidth.	CoRR	2018	DBLP BibTeX RDF
21	Vida Dujmovic, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood	Minor-closed graph classes with bounded layered pathwidth.	CoRR	2018	DBLP BibTeX RDF
21	Martin E. Dyer, Catherine S. Greenhill, Haiko Müller	Counting independent sets in graphs with bounded bipartite pathwidth.	CoRR	2018	DBLP BibTeX RDF
21	Hans L. Bodlaender, Tom C. van der Zanden	On Exploring Temporal Graphs of Small Pathwidth.	CoRR	2018	DBLP BibTeX RDF
21	Paz Carmi, Vida Dujmovic, Pat Morin	Anagram-Free Chromatic Number Is Not Pathwidth-Bounded.	WG	2018	DBLP DOI BibTeX RDF
21	Shai Vardi	Randomly Coloring Graphs of Logarithmically Bounded Pathwidth.	APPROX-RANDOM	2018	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.	CoRR	2017	DBLP BibTeX RDF
21	Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger	Treewidth and Pathwidth parameterized by the vertex cover number.	Discret. Appl. Math.	2017	DBLP DOI BibTeX RDF
21	Euripides Markou, Nicolas Nisse, Stéphane Pérennes	Exclusive graph searching vs. pathwidth.	Inf. Comput.	2017	DBLP DOI BibTeX RDF
21	Héctor Joaquín Fraire Huacuja, Norberto Castillo-García, Mario César López Locés, José Antonio Martínez Flores, Rodolfo A. Pazos Rangel, Juan Javier González Barbosa, Juan Martín Carpio Valadez	Integer Linear Programming Formulation and Exact Algorithm for Computing Pathwidth.	Nature-Inspired Design of Hybrid Intelligent Systems	2017	DBLP DOI BibTeX RDF